Divisibilité et division euclidienne

1.1 Diviseurs et multiples

Définition. Soit $a$ et $b$ deux entiers relatifs. On dit que $b$ divise $a$ s'il existe un entier relatif $k$ tel que $a = k\,b$. On note $b \mid a$ (on lit « $b$ divise $a$ »). On dit aussi que $b$ est un diviseur de $a$, ou que $a$ est un multiple de $b$.

Exemple 1.

• $6 \mid 42$, car $42 = 7 \times 6$ ;
• $-3 \mid 12$, car $12 = (-4) \times (-3)$ ;
• $5$ ne divise pas $12$ (on note $5 \nmid 12$) : $12$ est compris entre $2 \times 5 = 10$ et $3 \times 5 = 15$.

Remarques.

• Tout entier divise $0$, car $0 = 0 \times b$. Mais $0$ ne divise que $0$.
• $1$ et $-1$ divisent tout entier.
• $a$ et $-a$ ont les mêmes diviseurs. Si $a \neq 0$ et $b \mid a$, alors $|b| \leq |a|$ : un entier non nul a un nombre fini de diviseurs.
• Les multiples de $b$ forment l'ensemble $b\mathbb{Z} = \{\dots\,;-2b\,;-b\,;0\,;b\,;2b\,;\dots\}$.

Exemple 2. Les diviseurs positifs de $12$ sont $1$, $2$, $3$, $4$, $6$ et $12$. Dans $\mathbb{Z}$, $12$ a donc $12$ diviseurs : $\pm 1$, $\pm 2$, $\pm 3$, $\pm 4$, $\pm 6$, $\pm 12$.

1.2 Propriétés de la divisibilité

Soit $a$, $b$ et $c$ des entiers relatifs.

Démonstration de la deuxième propriété. Si $b = k\,a$ et $c = k'\,a$, alors $bu + cv = (ku + k'v)\,a$, et $ku + k'v$ est un entier.

Méthode : faire disparaître l'inconnue. Pour trouver les $n$ tels qu'une expression en $n$ divise une autre, on fabrique une combinaison des deux qui ne dépend plus de $n$.

Exemple 3. Déterminer les entiers naturels $n$ tels que $n + 2$ divise $3n + 11$.

$n + 2$ divise $n + 2$, donc il divise $3(n + 2) = 3n + 6$. S'il divise aussi $3n + 11$, il divise la différence : $(3n + 11) - (3n + 6) = 5$. Donc $n + 2$ est un diviseur positif de $5$ : $n + 2 = 1$ ou $n + 2 = 5$. Comme $n + 2 \geq 2$, il reste $n + 2 = 5$, soit $n = 3$.

Vérification : pour $n = 3$, $3n + 11 = 20$ et $n + 2 = 5$ divise bien $20$. La seule solution est $n = 3$.

1.3 Division euclidienne dans $\mathbb{N}$

Théorème. Soit $a \in \mathbb{N}$ et $b \in \mathbb{N}^*$. Il existe un unique couple $(q\,;r)$ d'entiers naturels tel que $a = b\,q + r \qquad \text{et} \qquad 0 \leq r < b.$ $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.

Exemple 4. $2\,026 = 7 \times 289 + 3$, et $0 \leq 3 < 7$ : le quotient de $2\,026$ par $7$ est $289$ et le reste est $3$.

Remarque. $b$ divise $a$ si, et seulement si, le reste de la division euclidienne de $a$ par $b$ est nul.

1.4 Division euclidienne dans $\mathbb{Z}$

Théorème. Soit $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$. Il existe un unique couple $(q\,;r)$, avec $q \in \mathbb{Z}$ et $r \in \mathbb{N}$, tel que $a = b\,q + r \qquad \text{et} \qquad 0 \leq r < |b|.$

Le reste est toujours positif ou nul, même si $a$ est négatif.

Exemple 5. Division euclidienne de $-17$ par $5$. On divise d'abord $17$ : $17 = 5 \times 3 + 2$, donc $-17 = 5 \times (-3) - 2$. Mais $-2$ n'est pas un reste, car il est négatif. On retire donc une fois $5$ au quotient et on l'ajoute au reste : $-17 = 5 \times (-4) + 3, \qquad 0 \leq 3 < 5.$ Le quotient est $-4$ et le reste est $3$.

Exemple 6. Division euclidienne de $17$ par $-5$ : $17 = (-5) \times (-3) + 2$, avec $0 \leq 2 < |-5| = 5$.

Démonstration (cas $b > 0$, non exigée).

• Existence. On prend pour $q$ la partie entière de $\dfrac{a}{b}$ (Seconde) : $q \leq \dfrac{a}{b} < q + 1$. En multipliant par $b > 0$ : $bq \leq a < bq + b$, donc $r = a - bq$ vérifie $0 \leq r < b$.
• Unicité. Si $a = bq + r = bq' + r'$ avec $0 \leq r < b$ et $0 \leq r' < b$, alors $b\,|q - q'| = |r' - r| < b$. L'entier naturel $|q - q'|$ est donc strictement inférieur à $1$ : il est nul, d'où $q = q'$ puis $r = r'$.

Pour $b < 0$, on divise $a$ par $|b| = -b$ : $a = (-b)\,q + r$, c'est-à-dire $a = b\,(-q) + r$.

1.5 Raisonner sur les restes

Dans la division par $n$, il n'y a que $n$ restes possibles : $0$, $1$, …, $n - 1$. Tout entier s'écrit donc sous l'une des formes $nk$, $nk + 1$, …, $nk + (n - 1)$, avec $k \in \mathbb{Z}$. On peut alors raisonner cas par cas.

Exemple 7. Montrer que, pour tout entier $n$, $n(n + 1)(2n + 1)$ est divisible par $3$.

Reste de $n$ par $3$	$n = 3k$	$n = 3k + 1$	$n = 3k + 2$
Facteur divisible par $3$	$n = 3k$	$2n + 1 = 6k + 3 = 3(2k + 1)$	$n + 1 = 3k + 3 = 3(k + 1)$

Dans chacun des trois cas, l'un des facteurs est un multiple de $3$, donc le produit aussi.