Divisibilité et congruences

Dans ce chapitre, les nombres étudiés sont des entiers relatifs. On dit que a divise b, et on écrit a | b, s’il existe un entier k tel que b = ak. Ainsi 4 divise 20 et −4 divise aussi 20. La relation ne signifie pas que a est plus petit que b : les signes peuvent varier. Tout entier divise zéro, puisque 0 = a × 0. En revanche, zéro ne divise aucun entier non nul, car un produit par zéro vaut toujours zéro.

Si un entier d divise a et b, alors il divise toute combinaison entière ua + vb. En effet, écrire a = dr et b = ds donne ua + vb = d(ur + vs), et ur + vs est entier. Cette propriété sert à transformer une expression compliquée en une expression plus simple. Si d divise a et si a divise b, alors d divise b : c’est la transitivité de la divisibilité.

Il faut distinguer un diviseur d’un quotient. Dans 20 = 4 × 5, les entiers 4 et 5 sont deux diviseurs de 20. L’écriture 20/4 donne un entier, mais 20/3 n’en donne pas. Pour étudier les diviseurs positifs d’un entier non nul, on peut chercher les couples de facteurs. Le carré d’un entier peut faire apparaître un facteur répété ; on ne doit pas compter deux fois la même valeur dans une liste de diviseurs.

Pour tout entier a et tout entier b strictement positif, il existe un unique couple d’entiers (q ; r) tel que a = bq + r et 0 ≤ r < b. C’est la division euclidienne de a par b. Le quotient q peut être négatif ; le reste r ne l’est jamais. L’inégalité stricte r < b est aussi importante que l’égalité. Une décomposition peut être juste sans être une division euclidienne si son reste est trop grand ou négatif.

On peut voir q comme le plus grand entier inférieur ou égal à a/b. Alors q ≤ a/b < q + 1 ; multiplier par b positif puis soustraire bq donne les bornes du reste. Pour l’unicité, supposons a = bq + r = bq′ + r′ avec deux restes admissibles. On a b(q − q′) = r′ − r. Le membre de droite est strictement compris entre −b et b ; le seul multiple de b dans cet intervalle est zéro. Donc q = q′ et r = r′.

Pour un entier n strictement positif, a et b sont congrus modulo n lorsque n divise a − b. On note a ≡ b [n]. Cette relation signifie aussi que les divisions euclidiennes de a et b par n donnent le même reste. Par exemple 17 ≡ 2 [5] et −3 ≡ 2 [5]. La congruence ne veut pas dire que les nombres sont égaux ; elle conserve seulement leur information de reste.

La congruence est réflexive, symétrique et transitive. Elle est compatible avec l’addition et la multiplication : si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n] et ac ≡ bd [n]. Pour le produit, ac − bd = a(c − d) + d(a − b), somme de multiples de n. En répétant la multiplication, aᵏ ≡ bᵏ [n] pour tout entier naturel k. Ces propriétés permettent de remplacer un grand nombre par un petit reste pendant un calcul.

On peut également soustraire des congruences ou multiplier les deux membres par un entier. En revanche, la division n’est pas libre : de 2x ≡ 2 [6], on ne déduit pas x ≡ 1 [6]. Le coefficient 2 masque une partie de l’information modulo 6. Pour annuler un facteur, il faut des hypothèses supplémentaires, étudiées avec les entiers premiers entre eux. De même, une puissance négative réclame l’existence d’un inverse modulo n ; elle n’est pas automatiquement définie.

Les congruences expliquent des tests familiers. Si un entier positif est écrit en base dix, il est somme de ses chiffres multipliés par des puissances de 10. Modulo 9, on a 10 ≡ 1, donc chaque puissance de 10 vaut 1 modulo 9. Le nombre est alors congru à la somme de ses chiffres. Il est divisible par 9 exactement lorsque cette somme l’est. Le même raisonnement fonctionne pour 3.

Modulo 11, 10 ≡ −1. Les puissances de 10 alternent donc entre 1 et −1. En partant du chiffre des unités, on additionne et soustrait alternativement les chiffres. Le nombre et cette somme alternée ont le même reste modulo 11. Pour 2728, on obtient 8 − 2 + 7 − 2 = 11 : il est divisible par 11. Une somme alternée négative ne pose aucun problème, puisque les congruences concernent aussi les entiers négatifs.

Résoudre ax ≡ b [n] signifie trouver tous les entiers x satisfaisant cette relation. Pour un petit module, on peut examiner les n restes possibles de x. Il suffit de tester x entre 0 et n − 1, car deux entiers de même reste donnent des produits ax de même reste. Chaque reste retenu correspond ensuite à une famille infinie x = r + kn, avec k entier. Donner seulement le représentant r ne décrit pas toutes les solutions entières.

Erreurs fréquentes : confondre diviseur et multiple ; accepter un reste négatif ; remplacer une congruence par une égalité ; simplifier un facteur comme dans une fraction. Relire les bornes, le module et le domaine des variables permet de repérer ces erreurs avant de conclure. Un calcul numérique peut découvrir un contre-exemple et invalider une affirmation générale ; quelques exemples favorables ne prouvent jamais cette affirmation pour tous les entiers.

Pour poursuivre, ouvre S’entraîner dans /exercices et choisis un exercice où tu dois expliquer la méthode autant que calculer. Tu peux aussi inventer une affirmation sur les restes, chercher à la réfuter avec de petits entiers, puis décider si elle mérite une preuve. Cette alternance entre expérimentation et démonstration prépare l’étude du PGCD et du théorème de Bézout.