Divisibilité et division euclidienne

La divisibilité dans les entiers

Dans la leçon sur les opérations sur les entiers naturels, on a dit qu’un entier naturel $b$ divise un autre entier naturel $a$, et on a écrit $b \mid a$, lorsque $a$ est un multiple de $b$. La définition s’étend sans changement aux entiers relatifs, dont la construction est étudiée dans la leçon sur les entiers relatifs : l’entier $b$ divise l’entier $a$ si $a$ est le produit de $b$ par un certain entier. Cette leçon appartient à l’unité suivante ; ici, les entiers relatifs sont utilisés par anticipation, et l’on admet sans démonstration les règles de leur arithmétique et de leur ordre qui y sont fondées : la règle des signes, le fait que le produit d’un entier par un entier naturel conserve le sens des inégalités, le fait qu’un facteur non nul peut être simplifié dans un produit, et le fait que les entiers relatifs sont les entiers naturels, $0$ et les opposés des entiers naturels. Leur démonstration exige la construction des entiers relatifs à partir des entiers naturels, qui n’utilise rien de cette leçon, de sorte qu’il n’y a pas de cercle.

On dit aussi que $b$ est un diviseur de $a$ et que $a$ est un multiple de $b$. De la définition découlent immédiatement quelques cas extrêmes : $0$ est un multiple de tout entier, car $0 = b \cdot 0$ ; les nombres $1$ et $-1$ divisent tout entier ; et $0$ ne divise que $0$, car $0 \cdot k = 0$ pour tout $k$. Or $a = bk$ équivaut à $-a = b(-k)$ et à $a = (-b)(-k)$ ; d’où $a$ et $-a$ ont les mêmes diviseurs, et $b$ et $-b$ divisent les mêmes nombres. C’est pourquoi, en pratique, il suffit d’étudier les diviseurs qui sont des entiers naturels.

Propriétés de la divisibilité

Pour tous les entiers $a$, $b$, $c$, $d$, $x$ et $y$, les propriétés suivantes sont vraies, et leurs démonstrations se ramènent à la définition :

1. Réflexivité : $a \mid a$, car $a = a \cdot 1$.
2. Transitivité : si $a \mid b$ et $b \mid c$, alors $a \mid c$. En effet, si $b = ak$ et $c = bl$, alors $c = a(kl)$.
3. Combinaisons linéaires : si $d \mid a$ et $d \mid b$, alors $d \mid ax + by$, comme le démontre la proposition suivante.
4. Encadrement : si $b \mid a$ et $a > 0$, alors $-a \leq b \leq a$. Il suffit de le voir pour $b > 0$ : dans ce cas $a = bk$ avec $k$ entier naturel, et comme $k \geq 1$, on a $a = b + b(k - 1) \geq b$.
5. Antisymétrie dans les entiers naturels : si $a$ et $b$ sont des entiers naturels, $a \mid b$ et $b \mid a$, alors $a = b$, car l’encadrement donne $a \leq b$ et $b \leq a$.

L’encadrement a une conséquence qui servira souvent : un entier non nul n’a qu’un nombre fini de diviseurs. De toutes les propriétés, la troisième est la plus féconde, et il convient de la retenir avec son énoncé complet et sa démonstration.

Lue dans l’autre sens, la propriété sert à écarter des diviseurs : si $d$ divise $a$ mais pas $b$, alors il ne divise pas $a + b$, car s’il le divisait, il diviserait aussi la différence $(a + b) - a = b$.