---
title: "Arithmétique : diviseurs et nombres premiers"
book: "Mathématiques du primaire et du collège"
subject: math
language: fr
chapter: 64
exercises: 10
source: https://one-course.com/books/math/1/fr/chapter/64-arithmetique-diviseurs-et-nombres-premiers
---

# Chapitre 64 — Arithmétique : diviseurs et nombres premiers

L’arithmétique étudie les nombres entiers et la façon dont ils se divisent les uns les autres. Ses personnages centraux sont les [nombres premiers](#def-g9-arith-prime), les briques de base à partir desquelles tout entier s’assemble par multiplication. Le chapitre se termine par le [plus grand commun diviseur](#def-g9-arith-gcd), l’outil juste pour simplifier les [fractions](https://one-course.com/books/math/1/fr/chapter/63-fractions-et-puissances#def-g9-fractions-fraction) une fois pour toutes. Cette histoire se poursuit, bien plus loin, dans les [volumes](https://one-course.com/books/math/1/fr/chapter/43-perimetre-aire-volume#def-g6-measure-volume) suivants de cette série et au-delà.

## 64.1 Diviseurs et multiples

**Définition 64.1 (Diviseur, multiple).**

Soient $a$ et $b$ des entiers positifs. On dit que $b$ *divise* $a$ (ou que $b$ est un diviseur de $a$, ou que $a$ est un *multiple* de $b$) lorsque $a = b \times k$ pour un certain entier $k$ — c’est-à-dire lorsque la division de $a$ par $b$ laisse un [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) $0$.

**Exemple 64.2.**

Les [diviseurs](#def-g9-arith-divisor) de $24$ sont $1, 2, 3, 4, 6, 8, 12, 24$ — ils viennent par paires dont le [produit](https://one-course.com/books/math/1/fr/chapter/10-multiplication-premiers-pas#def-g2-mult-def) est $24$ : $(1,24)$, $(2,12)$, $(3,8)$, $(4,6)$. Les [multiples](https://one-course.com/books/math/1/fr/chapter/32-division-et-multiples#def-g5-division-multiple) de $7$ sont $7, 14, 21, 28, \dots$

**Proposition 64.3 (Critères de divisibilité).**

Un entier est [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) :

- par $2$ lorsque son dernier chiffre est [pair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd) ( $0, 2, 4, 6, 8$ ) ;
- par $5$ lorsque son dernier chiffre est $0$ ou $5$ ;
- par $10$ lorsque son dernier chiffre est $0$ ;
- par $3$ (resp. $9$ ) lorsque la [somme](https://one-course.com/books/math/1/fr/chapter/2-addition-premiers-pas#def-g1-addition-def) de ses chiffres est [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $3$ (resp. $9$ ) ;
- par $4$ lorsque ses deux derniers chiffres forment un nombre [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $4$ .

**Démonstration.** *Admis à ce niveau.* ∎

**Exemple 64.4.**

$7\,215$ se termine par $5$ : [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $5$. Sa [somme](https://one-course.com/books/math/1/fr/chapter/2-addition-premiers-pas#def-g1-addition-def) de chiffres est $7 + 2 + 1 + 5 = 15$, [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $3$ mais pas par $9$ : donc $7\,215$ est [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $3$, pas par $9$. En effet $7\,215 = 3 \times 5 \times 481$.

## 64.2 Nombres premiers

**Définition 64.5 (Nombre premier).**

Un *nombre premier* est un entier $\geq 2$ dont les seuls [diviseurs](#def-g9-arith-divisor) sont $1$ et lui-même. Les premiers inférieurs à $30$ sont

$$
2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .
$$

Le nombre $1$ n’est *pas* premier (par convention), et un entier $\geq 2$ qui n’est pas premier s’appelle *composé*.

**Théorème 64.6 (Décomposition en facteurs premiers).**

Tout entier $\geq 2$ est un [produit](https://one-course.com/books/math/1/fr/chapter/10-multiplication-premiers-pas#def-g2-mult-def) de [nombres premiers](#def-g9-arith-prime), et cette décomposition est unique à l’ordre des facteurs près.

**Démonstration.** *Admis à ce niveau.* ∎

**Méthode 64.7 (Décomposer un entier).**

Diviser par le plus petit premier possible, de façon répétée, jusqu’à atteindre $1$ :

1. essayer $2$ tant que le nombre est [pair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd) ;
2. puis essayer $3$ , puis $5$ , puis $7$ , … (seulement des premiers) ;
3. s’arrêter lorsque le [quotient](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) est $1$ ; collecter les facteurs avec [exposants](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) .

Il suffit d’essayer les premiers $p$ avec $p^2$ ne dépassant pas le nombre courant : si aucun ne le [divise](#def-g9-arith-divisor), le nombre lui-même est premier.

**Exemple 64.8.**

Décomposer $360$, une division à la fois :

$$
360 = 2 \times 180, \quad
180 = 2 \times 90, \quad
90 = 2 \times 45, \quad
45 = 3 \times 15, \quad
15 = 3 \times 5,
$$

donc

$$
360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2
\times 5 .
$$

![L’arbre de facteurs de 360 : chaque étape détache le plus petit facteur premier (en rouge). En lisant les feuilles rouges et le 5 final : 360 = 23 × 32 × 5.](https://one-course.com/images/onecourse/chapters/math-1/g9-arith/fig-aae7345aa9ba.svg)

*L’arbre de facteurs de $360$ : chaque étape détache le plus petit facteur premier (en rouge). En lisant les feuilles rouges et le $5$ final : $360 = 2^3 \times 3^2 \times 5$.*

**Théorème 64.9 (Euclide).**

Il existe une infinité de [nombres premiers](#def-g9-arith-prime).

**Démonstration.** Supposons qu’il n’y en ait qu’un nombre fini, disons $p_1, p_2, \dots,
p_k$, et considérer

$$
N = p_1 \times p_2 \times \dots \times p_k + 1 .
$$

Diviser $N$ par n’importe quel $p_i$ laisse un [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) $1$, donc aucun $p_i$ ne [divise](#def-g9-arith-divisor) $N$. Mais $N \geq 2$ a au moins un [diviseur](#def-g9-arith-divisor) premier ([Théorème 64.6](#thm-g9-arith-factorization)) — un premier qui n’est pas dans notre liste. Contradiction : aucune liste finie ne peut contenir tous les premiers. ∎

## 64.3 Le plus grand commun diviseur

**Définition 64.10 (PGCD).**

Le *plus grand commun diviseur* de deux entiers positifs $a$ et $b$, noté $\gcd(a, b)$, est le plus grand entier divisant les deux. Lorsque $\gcd(a, b) = 1$, les entiers sont dits *premiers entre eux* : ils ne partagent aucun [diviseur](#def-g9-arith-divisor) excepté $1$.

**Exemple 64.11.**

[Diviseurs](#def-g9-arith-divisor) de $18$ : $1, 2, 3, 6, 9, 18$. [Diviseurs](#def-g9-arith-divisor) de $24$ : $1, 2, 3,
4, 6, 8, 12, 24$. [Diviseurs](#def-g9-arith-divisor) communs : $1, 2, 3, 6$ ; donc $\gcd(18, 24) = 6$. Les entiers $15$ et $28$ sont [premiers entre eux](#def-g9-arith-gcd).

**Proposition 64.12 (PGCD à partir des décompositions).**

Le [PGCD](#def-g9-arith-gcd) de deux entiers est le [produit](https://one-course.com/books/math/1/fr/chapter/10-multiplication-premiers-pas#def-g2-mult-def) des premiers apparaissant dans *les deux* décompositions, chacun pris avec le *plus petit* de ses deux [exposants](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def).

**Démonstration.** *Admis à ce niveau.* ∎

**Exemple 64.13.**

$360 = 2^3 \times 3^2 \times 5$ et $84 = 2^2 \times 3 \times 7$. Premiers communs : $2$ ([exposants](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) $3$ et $2$ : garder $2$) et $3$ ([exposants](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) $2$ et $1$ : garder $1$). Donc

$$
\gcd(360, 84) = 2^2 \times 3 = 12 .
$$

**Théorème 64.14 (Algorithme d’Euclide).**

Si $a = bq + r$ est la division de $a$ par $b$ avec [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) $r$, alors

$$
\gcd(a, b) = \gcd(b, r).
$$

En répétant les divisions jusqu’à ce que le [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) soit $0$, le [PGCD](#def-g9-arith-gcd) de $a$ et $b$ est le *dernier [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) non nul*.

**Démonstration.** De $a = bq + r$ : tout entier divisant $b$ et $r$ [divise](#def-g9-arith-divisor) $bq + r = a$ ; et de $r = a - bq$ : tout entier divisant $a$ et $b$ [divise](#def-g9-arith-divisor) $r$. Donc les paires $(a, b)$ et $(b, r)$ ont exactement les mêmes [diviseurs](#def-g9-arith-divisor) communs — en particulier le même plus grand. Puisque les [restes](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) décroissent strictement, l’algorithme se termine, et $\gcd(x, 0) = x$ donne le dernier [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) non nul. ∎

**Exemple 64.15.**

Calculer $\gcd(1071, 462)$ :

$$
\begin{align*}
1071 &= 462 \times 2 + 147, \\
462 &= 147 \times 3 + 21, \\
147 &= 21 \times 7 + 0 .
\end{align*}
$$

Le dernier [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) non nul est $21$ : $\gcd(1071, 462) = 21$.

**Méthode 64.16 (Simplifier complètement une fraction).**

Pour écrire $\dfrac ab$ sous forme irréductible :

1. calculer $d = \gcd(a, b)$ , par ex. par l’algorithme d’Euclide ;
2. diviser [numérateur](https://one-course.com/books/math/1/fr/chapter/24-premieres-fractions#def-g4-fractions-def) et [dénominateur](https://one-course.com/books/math/1/fr/chapter/24-premieres-fractions#def-g4-fractions-def) par $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
3. la [fraction](https://one-course.com/books/math/1/fr/chapter/63-fractions-et-puissances#def-g9-fractions-fraction) résultante est *irréductible* : son [numérateur](https://one-course.com/books/math/1/fr/chapter/24-premieres-fractions#def-g4-fractions-def) et son [dénominateur](https://one-course.com/books/math/1/fr/chapter/24-premieres-fractions#def-g4-fractions-def) sont [premiers entre eux](#def-g9-arith-gcd) .

**Exemple 64.17.**

$\dfrac{462}{1071} = \dfrac{462 \div 21}{1071 \div 21} = \dfrac{22}{51}$, et $\gcd(22, 51) = 1$ : irréductible.

## 64.4 Exercices

**Exercice 64.1 ★.**

Lister tous les [diviseurs](#def-g9-arith-divisor) de $36$, de $45$, et de $17$.

**Solution de Exercice 64.1.**

[Diviseurs](#def-g9-arith-divisor) de $36$ : $1, 2, 3, 4, 6, 9, 12, 18, 36$. [Diviseurs](#def-g9-arith-divisor) de $45$ : $1, 3, 5, 9, 15, 45$. [Diviseurs](#def-g9-arith-divisor) de $17$ : $1$ et $17$ seulement ($17$ est premier).

**Exercice 64.2 ★.**

En utilisant les critères de divisibilité, déterminer si $2\,346$ est [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $2$, par $3$, par $4$, par $5$, par $9$.

**Solution de Exercice 64.2.**

$2\,346$ se termine par $6$ : [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $2$, pas par $5$. [Somme](https://one-course.com/books/math/1/fr/chapter/2-addition-premiers-pas#def-g1-addition-def) des chiffres $2 + 3 + 4 + 6 = 15$ : [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $3$, pas par $9$. Les deux derniers chiffres $46$, et $46 = 4 \times 11 + 2$ n’est pas [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $4$ : $2\,346$ n’est pas [divisible](https://one-course.com/books/math/1/fr/chapter/37-les-nombres-entiers#def-g6-wholes-divisible) par $4$.

**Exercice 64.3 ★.**

Donner la décomposition en facteurs premiers de $72$, $150$, $210$ et $121$.

**Solution de Exercice 64.3.**

$72 = 2^3 \times 3^2$ ; $150 = 2 \times 3 \times 5^2$ ; $210 = 2 \times 3 \times 5 \times 7$ ; $121 = 11^2$.

**Exercice 64.4 ★.**

$101$ est-il premier ? $91$ ? $143$ ? Justifier en utilisant la règle d’arrêt de [Méthode 64.7](#met-g9-arith-factorization).

**Solution de Exercice 64.4.**

$101$ : tester les premiers $p$ avec $p^2 \leq 101$, c’est-à-dire $2,
3, 5, 7$. Aucun ne [divise](#def-g9-arith-divisor) $101$ ([impair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd), [somme](https://one-course.com/books/math/1/fr/chapter/2-addition-premiers-pas#def-g1-addition-def) des chiffres $2$, ne se termine pas par $0/5$, $101 = 7 \times 14 + 3$) : $101$ est premier.

$91 = 7 \times 13$ : pas premier.

$143 = 11 \times 13$ : pas premier.

**Exercice 64.5 ★.**

Calculer $\gcd(48, 60)$ de deux façons : en listant les [diviseurs](#def-g9-arith-divisor) communs, et à partir des décompositions en facteurs premiers.

**Solution de Exercice 64.5.**

[Diviseurs](#def-g9-arith-divisor) communs de $48$ et $60$ : [diviseurs](#def-g9-arith-divisor) de $48$ : $1, 2, 3, 4, 6,
8, 12, 16, 24, 48$ ; [diviseurs](#def-g9-arith-divisor) de $60$ : $1, 2, 3, 4, 5, 6, 10, 12, 15,
20, 30, 60$ ; les communs sont $1, 2, 3, 4, 6, 12$, donc $\gcd(48,60) = 12$.

Par décomposition : $48 = 2^4 \times 3$ et $60 = 2^2 \times 3 \times 5$ ; premiers communs avec plus petits [exposants](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) : $2^2 \times 3 = 12$.

**Exercice 64.6 ★★.**

Utiliser l’algorithme d’Euclide pour calculer $\gcd(255, 154)$, puis $\gcd(1053, 325)$. Écrire chaque ligne de division.

**Solution de Exercice 64.6.**

$\gcd(255, 154)$ :

$$
\begin{align*}
255 &= 154 \times 1 + 101, \\
154 &= 101 \times 1 + 53, \\
101 &= 53 \times 1 + 48, \\
53 &= 48 \times 1 + 5, \\
48 &= 5 \times 9 + 3, \\
5 &= 3 \times 1 + 2, \\
3 &= 2 \times 1 + 1, \\
2 &= 1 \times 2 + 0 .
\end{align*}
$$

Dernier [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) non nul : $\gcd(255, 154) = 1$ (ils sont [premiers entre eux](#def-g9-arith-gcd)).

$\gcd(1053, 325)$ :

$$
\begin{align*}
1053 &= 325 \times 3 + 78, \\
325 &= 78 \times 4 + 13, \\
78 &= 13 \times 6 + 0 .
\end{align*}
$$

$\gcd(1053, 325) = 13$.

**Exercice 64.7 ★★.**

Rendre irréductible la [fraction](https://one-course.com/books/math/1/fr/chapter/63-fractions-et-puissances#def-g9-fractions-fraction) $\dfrac{588}{504}$. (Calculer le [PGCD](#def-g9-arith-gcd) par la méthode de son choix, puis diviser.)

**Solution de Exercice 64.7.**

Algorithme d’Euclide : $588 = 504 \times 1 + 84$ ; $504 = 84 \times 6 +
0$ : $\gcd(588, 504) = 84$. Puis

$$
\frac{588}{504} = \frac{588 \div 84}{504 \div 84} = \frac{7}{6},
$$

qui est irréductible.

**Exercice 64.8 ★★.**

Une fleuriste a $84$ roses et $126$ tulipes et veut faire des bouquets identiques, en utilisant toutes les fleurs, avec autant de bouquets que possible. Combien de bouquets peut-elle faire, et que contient chacun ?

**Solution de Exercice 64.8.**

Le nombre de bouquets doit diviser à la fois $84$ et $126$ ; le plus grand possible est $\gcd(84, 126)$. Décompositions : $84 = 2^2 \times 3
\times 7$, $126 = 2 \times 3^2 \times 7$, donc le [PGCD](#def-g9-arith-gcd) est $2 \times 3
\times 7 = 42$. Elle peut faire $42$ bouquets, chacun contenant $\frac{84}{42} = 2$ roses et $\frac{126}{42} = 3$ tulipes.

**Exercice 64.9 ★★.**

Deux ferries quittent le même quai à 8:00. L’un part toutes les $24$ minutes, l’autre toutes les $36$ minutes. À quelle heure repartent-ils ensemble la prochaine fois ? (Chercher le plus petit [multiple](#def-g9-arith-divisor) commun de $24$ et $36$ ; les décompositions aident.)

**Solution de Exercice 64.9.**

On cherche le plus petit [multiple](#def-g9-arith-divisor) commun. $24 = 2^3 \times 3$ et $36 = 2^2 \times 3^2$ ; en prenant chaque premier avec le *plus grand* [exposant](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) : $\operatorname{ppcm} = 2^3 \times 3^2 = 72$. Les ferries repartent ensemble $72$ minutes après 8:00, à 9:12.

**Exercice 64.10 ★★★.**

Soit $n$ un entier positif.

1. Montrer que $\gcd(n, n+1) = 1$ (les entiers consécutifs sont toujours [premiers entre eux](#def-g9-arith-gcd) ).
2. En déduire que la [fraction](https://one-course.com/books/math/1/fr/chapter/63-fractions-et-puissances#def-g9-fractions-fraction) $\dfrac{n}{n+1}$ est toujours irréductible.

**Solution de Exercice 64.10.**

*1.* Tout [diviseur](#def-g9-arith-divisor) commun $d$ de $n$ et $n+1$ [divise](#def-g9-arith-divisor) aussi leur [différence](https://one-course.com/books/math/1/fr/chapter/3-soustraction-premiers-pas#ex-g1-subtraction-difference) $(n+1) - n = 1$, donc $d = 1$ : $\gcd(n, n+1) = 1$.

*2.* Une [fraction](https://one-course.com/books/math/1/fr/chapter/63-fractions-et-puissances#def-g9-fractions-fraction) est irréductible exactement lorsque son [numérateur](https://one-course.com/books/math/1/fr/chapter/24-premieres-fractions#def-g4-fractions-def) et son [dénominateur](https://one-course.com/books/math/1/fr/chapter/24-premieres-fractions#def-g4-fractions-def) sont [premiers entre eux](#def-g9-arith-gcd), ce qui est le cas pour $n$ et $n + 1$ par le point 1.

## 64.5 Problème : des brocs d’eau, des cigales et cent casiers

**Problème 64.1.**

Devoir maison — le PGCD décide quelles quantités deux brocs peuvent mesurer ; les nombres premiers protègent les cigales ; et les casiers qui restent ouverts sont les carrés parfaits

Trois énigmes qui ressemblent à des devinettes et qui sont en réalité de l’arithmétique : mesurer de l’eau avec des brocs sans graduation (le [PGCD](#def-g9-arith-gcd) déguisé), des cycles de vie d’insectes que l’évolution a poussés vers les [nombres premiers](#def-g9-arith-prime), et un célèbre couloir de cent casiers dont l’état final se décide en comptant des [diviseurs](#def-g9-arith-divisor). Tout repose sur la machinerie de ce chapitre : la divisibilité, la décomposition en facteurs premiers ([Théorème 64.6](#thm-g9-arith-factorization)) et l’algorithme d’Euclide ([Théorème 64.14](#thm-g9-arith-euclidalgo)).

**Partie I — Les brocs d’eau.** Nous voici devant une fontaine avec deux brocs sans graduation, de $5$ L et $3$ L. Gestes autorisés : remplir un broc à ras bord, vider complètement un broc, verser un broc dans l’autre jusqu’à ce que la source soit vide ou que la cible soit pleine.

1. Mesurer exactement $1$ L. (Décrire la suite de gestes et le contenu des deux brocs après chacun d’eux.)
2. Mesurer exactement $4$ L — l’énigme d’un célèbre film d’action. (Six gestes suffisent.)
3. Quels nombres entiers de litres de $1$ à $8$ peut-on exhiber (dans un broc, ou répartis entre les deux) ? Compléter la liste, en réutilisant les suites de gestes déjà trouvées.
4. Nouveaux brocs : $6$ L et $4$ L. Essayer de mesurer $1$ L — puis expliquer pourquoi c’est sans espoir : vérifier que chacun des trois gestes autorisés maintient le contenu de chaque broc [multiple](#def-g9-arith-divisor) de $2$ , de sorte que toute quantité atteignable est paire.
5. L’argument de la question 4 vaut en général : avec des brocs de $a$ et $b$ litres, toute quantité atteignable est un [multiple](#def-g9-arith-divisor) de $\gcd(a, b)$ . Calculer $\gcd(6, 4)$ et $\gcd(5, 3)$ , et dire ce que la loi prédit pour chaque couple de brocs.

**Partie II — Euclide à la fontaine.**

6. Calculer par l’algorithme d’Euclide : $\gcd(91, 65)$ et $\gcd(2\,026, 46)$ .
7. Expliquer avec ses propres mots pourquoi les quantités qui apparaissent dans les brocs sont les [restes](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) d’Euclide déguisés : avec des brocs de $13$ L et $5$ L, remplir plusieurs fois le petit broc et le verser dans le grand (en vidant le grand chaque fois qu’il déborde). Quelles quantités nouvelles apparaissent en premier — et les comparer aux [restes](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) de l’algorithme d’Euclide pour $(13, 5)$ .
8. En déduire la réponse du champion : avec des brocs de $13$ et $5$ litres, peut-on mesurer exactement $1$ L ? Justifier en une ligne à l’aide de la question 5 et de $\gcd(13, 5)$ .
9. Une démonstration rapide de primalité entre eux, dans le style de l’ [Exercice 64.10](#exo-g9-arith-10) : montrer que $\gcd(n, 2n + 1) = 1$ pour tout entier $n$ strictement positif. (Que doit diviser un [diviseur](#def-g9-arith-divisor) commun de $n$ et de $2n + 1$ ?)
10. Deux bus quittent le terminus ensemble à 7 h 00 ; l’un part toutes les $12$ minutes, l’autre toutes les $18$ . Dresser la liste des départs suivants de chacun et trouver le premier instant où ils repartent ensemble. Vérifier sur cet exemple la belle loi : (premier [multiple](#def-g9-arith-divisor) commun) $\times$ [PGCD](#def-g9-arith-gcd) $=$ [produit](https://one-course.com/books/math/1/fr/chapter/10-multiplication-premiers-pas#def-g2-mult-def) des deux nombres — et la tester à nouveau sur $5$ et $3$ .

**Partie III — Cigales, [diviseurs](#def-g9-arith-divisor) et casiers.**

11. Certaines cigales d’Amérique du Nord ne sortent de terre que tous les $17$ ans ; supposons que la population d’un prédateur culmine tous les $4$ ans. Si les deux se produisent cette année, dans combien d’années une sortie coïncidera-t-elle de nouveau avec un pic ? Même question si le cycle des cigales était de $16$ ans — à quelle [fréquence](https://one-course.com/books/math/1/fr/chapter/50-organiser-des-donnees#def-g7-stats-frequency) seraient-elles alors massacrées ? Expliquer en une phrase pourquoi l’évolution a poussé le cycle vers une durée *première* .
12. À l’aide de la décomposition $360 = 2^3 \times 3^2 \times 5$ , compter les [diviseurs](#def-g9-arith-divisor) de $360$ sans les énumérer : un [diviseur](#def-g9-arith-divisor) choisit un [exposant](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) pour $2$ (quatre choix : $0, 1, 2, 3$ ), un pour $3$ , un pour $5$ . Combien de [diviseurs](#def-g9-arith-divisor) en tout ?
13. Montrer que, dans la décomposition d’un carré parfait $n = m^2$ , chaque [nombre premier](#def-g9-arith-prime) porte un [exposant](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) *[pair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd)* . En déduire, sans calculer aucune racine carrée, que $360$ n’est pas un carré parfait.
14. Associer à chaque [diviseur](#def-g9-arith-divisor) $d$ de $n$ son partenaire $\frac{n}{d}$ (pour $n = 36$ : $1 \leftrightarrow 36$ , $2 \leftrightarrow 18$ , $3 \leftrightarrow 12$ , $4 \leftrightarrow 9$ , $6 \leftrightarrow 6$ ). Quand un [diviseur](#def-g9-arith-divisor) est-il son propre partenaire ? En déduire le critère : $n$ a un nombre *[impair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd)* de [diviseurs](#def-g9-arith-divisor) exactement lorsque $n$ est un carré parfait. Le vérifier sur $36$ et sur $360$ .
15. Les cent casiers. Les casiers $1$ à $100$ sont d’abord tous fermés. L’élève $1$ change l’état de tous les casiers ; l’élève $2$ change l’état des casiers $2, 4, 6, \dots$ ; l’élève $k$ change l’état des [multiples](https://one-course.com/books/math/1/fr/chapter/32-division-et-multiples#def-g5-division-multiple) de $k$ ; et ainsi de suite jusqu’à l’élève $100$ . Expliquer quels élèves touchent le casier $n$ , combien de fois son état change, et — à l’aide de la question 14 — exactement quels casiers finissent ouverts. Combien y en a-t-il ?

**Solution de Problème 64.1.**

**1.** Remplir le $3$ et le verser dans le $5$ (contenus : $0/3 \to 3$ dans le grand). Remplir de nouveau le $3$ et le verser dans le $5$ jusqu’à ce qu’il soit plein : le grand broc n’accepte plus que $2$, il reste donc

$$
3 - 2 = 1 \text{ L dans le petit broc.}
$$

Gestes : remplir le $3$ ; verser $3 \to 5$ ; remplir le $3$ ; verser $3 \to 5$.

**2.** Remplir le $5$ ; verser dans le $3$ (il reste $2$ dans le grand) ; vider le $3$ ; y verser les $2$ ; remplir le $5$ ; verser dans le $3$ jusqu’à le remplir — il n’accepte que $1$, ce qui laisse $\mathbf{4}$ L dans le grand broc. Six gestes.

**3.** Tous : $1$ (question 1), $2$ (après deux gestes de la question 2), $3$ et $5$ (simples remplissages), $4$ (question 2), $6 = 3 + 3$ (un petit broc plein plus $3$ versés dans le grand), $7 = 5 + 2$, $8 = 5 + 3$ (les deux pleins). Toute quantité entière de $1$ à $8$ L est mesurable avec le $5$ et le $3$.

**4.** Au départ, les deux brocs contiennent $0$, un [multiple](#def-g9-arith-divisor) de $2$. Remplir fixe un contenu à $6$ ou $4$ : [pair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd). Vider le fixe à $0$ : [pair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd). Verser déplace de l’eau entre des brocs dont les contenus étaient [pairs](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd), et la quantité versée est une [différence](https://one-course.com/books/math/1/fr/chapter/3-soustraction-premiers-pas#ex-g1-subtraction-difference) de [nombres pairs](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd) (la place disponible, ou la quantité présente) : tous les contenus restent donc [pairs](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd) à jamais. Une cible impaire comme $1$ L est inatteignable.

**5.** $\gcd(6, 4) = 2$ : seules des quantités paires — confirmé par la question 4. $\gcd(5, 3) = 1$ : la loi autorise toute quantité entière, et la question 3 les a toutes réalisées. Le [PGCD](#def-g9-arith-gcd) est exactement l’unité de mesure des brocs.

**6.** $91 = 1 \times 65 + 26$ ; $65 = 2 \times 26 + 13$ ; $26 = 2 \times 13 + 0$ : $\gcd(91, 65) = 13$. Et $2\,026 = 44 \times 46 + 2$ ; $46 = 23 \times 2 + 0$ : $\gcd(2\,026, 46) = 2$.

**7.** En versant plusieurs fois le $5$ dans le broc de $13$ : après deux remplissages, le grand broc contient $10$ ; le troisième remplissage n’y entre qu’à hauteur de $3$, laissant $5 - 3 = 2$ dans le petit broc — or le [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) de $13$ par $5$ valait $3$, et les quantités $3$ (la place) et $2$ (le reliquat) sont exactement les nombres d’Euclide ($13 = 2 \times 5 + 3$, $5 = 1 \times 3 + 2$). En continuant, $3 - 2 = 1$ apparaît : le [reste](https://one-course.com/books/math/1/fr/chapter/17-partage-et-division#def-g3-division-remainder) suivant de l’algorithme. La fontaine effectue les divisions d’Euclide avec de l’eau.

**8.** $\gcd(13, 5) = 1$, donc la loi de la question 5 autorise toute quantité entière — et la cascade de la question 7 a effectivement [produit](https://one-course.com/books/math/1/fr/chapter/10-multiplication-premiers-pas#def-g2-mult-def) $1$ L. Oui.

**9.** Un [diviseur](#def-g9-arith-divisor) commun de $n$ et de $2n + 1$ [divise](#def-g9-arith-divisor) $2n + 1 - 2 \times n = 1$ : il vaut donc $1$. D’où $\gcd(n, 2n+1) = 1$ toujours.

**10.** Bus A : 7 h 12, 7 h 24, 7 h 36, 7 h 48, 8 h 00 … ; bus B : 7 h 18, 7 h 36, 7 h 54 … Premier départ commun : 7 h 36, au bout de $36$ minutes — le premier [multiple](#def-g9-arith-divisor) commun de $12$ et $18$. Loi : $36 \times \gcd(12, 18) = 36 \times 6 = 216 = 12 \times 18$. Pour $5$ et $3$ : premier [multiple](#def-g9-arith-divisor) commun $15$, et $15 \times \gcd(5,3) = 15 \times 1 = 15 = 5 \times 3$.

**11.** Avec un cycle de $17$ ans : la coïncidence suivante est le premier [multiple](#def-g9-arith-divisor) commun de $17$ et de $4$ ; comme $\gcd(17, 4) = 1$, c’est $17 \times 4 = 68$ ans — les cigales ne croisent le pic qu’une fois sur quatre sorties. Avec un cycle de $16$ ans : $16$ est un [multiple](#def-g9-arith-divisor) de $4$, donc *chaque* sortie tombe sur un pic. Une durée de cycle première ne partage aucun facteur avec un cycle de prédateur plus court, ce qui espace au maximum les coïncidences : l’arithmétique comme camouflage.

**12.** Quatre choix d’[exposant](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) pour $2$, trois pour $3$, deux pour $5$ : $4 \times 3 \times 2 = 24$ [diviseurs](#def-g9-arith-divisor).

**13.** Si $m = 2^{a} \times 3^{b} \times \cdots$, alors $m^2 = 2^{2a} \times 3^{2b} \times \cdots$ : chaque [exposant](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) est doublé, donc [pair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd). Or dans $360 = 2^3 \times 3^2 \times 5$, les [exposants](https://one-course.com/books/math/1/fr/chapter/56-puissances#def-g8-powers-def) de $2$ et de $5$ sont [impairs](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd) : $360$ n’est pas un carré parfait.

**14.** Un [diviseur](#def-g9-arith-divisor) est son propre partenaire exactement lorsque $d = \frac nd$, c’est-à-dire $n = d^2$ : seuls les carrés possèdent un tel [diviseur](#def-g9-arith-divisor) central. Pour tout autre $n$, les [diviseurs](#def-g9-arith-divisor) se répartissent en paires, donc en [nombre pair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd). Ainsi : [nombre impair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd) de [diviseurs](#def-g9-arith-divisor) $\Leftrightarrow$ carré parfait. Vérification : $36$ a pour [diviseurs](#def-g9-arith-divisor) $1, 2, 3, 4, 6, 9, 12, 18, 36$ — neuf, un [nombre impair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd), et $36 = 6^2$ ; tandis que $360$ en a $24$ (question 12), un [nombre pair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd), et n’est pas un carré (question 13).

**15.** Le casier $n$ change d’état une fois par élève $k$ dont le numéro [divise](#def-g9-arith-divisor) $n$ : en tout, autant de fois que $n$ a de [diviseurs](#def-g9-arith-divisor). Un casier finit *ouvert* lorsque son état a changé un [nombre impair](https://one-course.com/books/math/1/fr/chapter/14-les-nombres-jusqua-10-000#def-g3-numbers-evenodd) de fois — d’après la question 14, exactement lorsque $n$ est un carré parfait. Casiers ouverts : $1, 4, 9, 16, 25, 36, 49, 64, 81, 100$ — il y en a dix.