Divisibilité et congruences en L1 de maths : cours et méthodes

L’écriture \(b \mid a\) (lire « \(b\) divise \(a\) ») signifie que \(a = kb\) pour au moins un entier relatif \(k\). Dans ce cas, \(a\) est appelé multiple de \(b\), et \(b\) diviseur de \(a\). Les multiples de \(b\) forment l’ensemble \(b\mathbf{Z}\).

La relation de divisibilité est réflexive et transitive. De plus, si \(d \mid a\) et \(d \mid b\), alors \(d\) divise toute combinaison \(ua + vb\) avec \(u, v \in \mathbf{Z}\). Enfin, \(a \mid b\) et \(b \mid a\) entraînent \(|a| = |b|\).

Pour la combinaison, écrivons \(a = d a^{\prime}\) et \(b = d b^{\prime}\). Alors \(ua + vb = d(u a^{\prime} + v b^{\prime})\), qui est bien un multiple de \(d\). Pour le dernier point, supposons \(b = ka\) et \(a = \ell b\). Si \(a = 0\), alors \(b = 0\). Sinon, \(a = k \ell a\) donne \(k \ell = 1\). Les seuls entiers inversibles étant \(1\) et \(-1\), on obtient \(k = \pm 1\).

Sur \(\mathbf{Z}\), la divisibilité n’est pas antisymétrique. En effet, \(4 \mid -4\) et \(-4 \mid 4\), alors que \(4 \neq -4\). Ce n’est donc pas une relation d’ordre sur \(\mathbf{Z}\). En revanche, elle en devient une sur \(\mathbf{N}\).

Pour \(a \in \mathbf{Z}\) et \(b \geqslant 1\), on peut écrire \(a = bq + r\) avec \(q \in \mathbf{Z}\) et \(r \in \{0, 1, \dots, b – 1\}\), et ce d’une seule façon. On nomme \(q\) le quotient et \(r\) le reste.

Existence. Considérons \(A = \{a – bk \mid k \in \mathbf{Z}\} \cap \mathbf{N}\). Cette partie n’est pas vide : avec \(k = -|a|\), on obtient \(a + b|a| \geqslant a + |a| \geqslant 0\). Elle admet donc un plus petit élément \(r = a – bq\). Si l’on avait \(r \geqslant b\), alors \(r – b = a – b(q+1)\) serait encore dans \(A\) et plus petit que \(r\). C’est impossible, donc \(0 \leqslant r < b\).

Unicité. Supposons \(bq + r = bq^{\prime} + r^{\prime}\) avec les deux restes dans \([0, b – 1]\). Alors \(b \mid r – r^{\prime}\). Or \(|r – r^{\prime}| < b\). Le seul multiple de \(b\) de valeur absolue strictement inférieure à \(b\) est 0. Ainsi, \(r = r^{\prime}\), puis \(q = q^{\prime}\).

Divisons \(-47\) par 6. Le plus grand multiple de 6 inférieur ou égal à \(-47\) est \(-48 = 6 \times (-8)\). Par conséquent, \(-47 = 6 \times (-8) + 1\). Le quotient vaut \(-8\) et le reste vaut 1. On vérifie bien que \(0 \leqslant 1 < 6\).

Supposons \((a, b) \neq (0, 0)\). Les diviseurs communs à \(a\) et \(b\) contiennent 1 et sont bornés par \(\max(|a|, |b|)\). Le plus grand d’entre eux est le PGCD, noté \(a \wedge b\) ; on pose aussi \(0 \wedge 0 = 0\). Lorsque ce PGCD vaut 1, les deux entiers sont dits premiers entre eux.

Si \(a = bq + r\), alors les diviseurs communs à \(a\) et \(b\) sont exactement les diviseurs communs à \(b\) et \(r\). En particulier, \(a \wedge b = b \wedge r\).

Un diviseur commun à \(a\) et \(b\) divise la combinaison \(r = a – qb\). Inversement, un diviseur commun à \(b\) et \(r\) divise \(a = bq + r\). Ayant les mêmes éléments, ces deux ensembles ont le même maximum.

Calculons \(1078 \wedge 322\). Les divisions successives donnent : \[\begin{aligned} 1078 &= 3 \times 322 + 112, \\ 322 &= 2 \times 112 + 98, \\ 112 &= 1 \times 98 + 14, \\ 98 &= 7 \times 14 + 0. \end{aligned}\] Le dernier reste non nul vaut 14. Par conséquent, \(1078 \wedge 322 = 14\).

1. On écrit toutes les divisions de l’algorithme, en isolant chaque reste : \(r = a – qb\).
2. On part de l’avant-dernière égalité, qui exprime le PGCD.
3. On y remplace le reste précédent par son expression, puis on regroupe.
4. On recommence jusqu’à ne plus voir apparaître que \(a\) et \(b\).
5. On contrôle enfin la relation obtenue en effectuant les deux produits : les fautes de signe sont fréquentes.

Reprenons \(a = 1078\) et \(b = 322\). La troisième division donne \(14 = 112 – 98\). Or \(98 = 322 – 2 \times 112\), donc \(14 = 3 \times 112 – 322\). Ensuite, \(112 = 1078 – 3 \times 322\). En remplaçant, on obtient \[14 = 3 \times 1078 – 10 \times 322.\] Vérification : \(3234 – 3220 = 14\).

Le PGCD \(d\) de deux entiers \(a\) et \(b\) s’écrit toujours \(d = au + bv\) avec \(u, v\) entiers. En outre, la condition \(a \wedge b = 1\) équivaut à l’existence d’entiers \(u, v\) vérifiant \(au + bv = 1\).

Le premier point découle de l’algorithme d’Euclide étendu. Pour l’équivalence, le sens direct en est un cas particulier. Réciproquement, supposons \(au + bv = 1\). Tout diviseur commun à \(a\) et \(b\) divise alors 1. Il vaut donc \(\pm 1\), et le PGCD est égal à 1.

Si \(a \mid bc\) et si \(a \wedge b = 1\), alors \(a \mid c\).

Par Bézout, il existe \(u, v\) avec \(au + bv = 1\). Multiplions par \(c\) : \(c = acu + bcv\). Le premier terme est un multiple de \(a\). Le second aussi, car \(a \mid bc\). Donc \(a\) divise leur somme, c’est-à-dire \(c\).

L’hypothèse \(a \wedge b = 1\) est indispensable. Par exemple, 10 divise \(4 \times 15 = 60\). Pourtant, 10 ne divise ni 4 ni 15. Ici, \(10 \wedge 4 = 2\) et le lemme ne s’applique pas.

Si \(a \mid c\), \(b \mid c\) et \(a \wedge b = 1\), alors \(ab \mid c\). De plus, un entier premier avec \(b\) et premier avec \(c\) reste premier avec le produit \(bc\).

Soit \(a\) et \(b\) non nuls. Le produit \(|ab|\) est un multiple commun strictement positif ; il en existe donc un plus petit. On l’appelle PPCM de \(a\) et \(b\) et on le note \(a \vee b\).

Lorsque \(a\) et \(b\) sont strictement positifs, le produit du PGCD par le PPCM redonne \(ab\). Par ailleurs, un entier est multiple commun de \(a\) et \(b\) exactement quand il est multiple de \(a \vee b\).

Posons \(d = a \wedge b\), puis \(a = d a^{\prime}\) et \(b = d b^{\prime}\), avec \(a^{\prime} \wedge b^{\prime} = 1\). Soit \(m\) un multiple commun : \(m = a k = d a^{\prime} k\). Comme \(b \mid m\), on obtient \(b^{\prime} \mid a^{\prime} k\), donc \(b^{\prime} \mid k\) par Gauss. Ainsi, \(m\) est un multiple de \(d a^{\prime} b^{\prime}\). Réciproquement, \(d a^{\prime} b^{\prime}\) est un multiple commun. Finalement, \(a \vee b = d a^{\prime} b^{\prime}\), et \(d \times d a^{\prime} b^{\prime} = ab\).

Prenons \(a, b\) non nuls, de PGCD \(d\). Pour que \(ax + by = c\) possède au moins une solution dans \(\mathbf{Z}^2\), il faut et il suffit que \(d\) divise \(c\). Une solution \((x_0, y_0)\) étant connue, toutes les autres s’obtiennent sous la forme \[\left(x_0 + k \frac{b}{d},\ y_0 – k \frac{a}{d}\right), \qquad k \in \mathbf{Z}.\]

1. On calcule \(d = a \wedge b\) et l’on vérifie que \(d \mid c\) ; sinon, il n’y a aucune solution.
2. On divise l’équation par \(d\) pour se ramener à des coefficients premiers entre eux.
3. On cherche un premier couple solution, soit de tête, soit en remontant l’algorithme d’Euclide.
4. On soustrait les deux égalités et l’on applique le lemme de Gauss.
5. On écrit la famille de solutions, puis on la vérifie en la réinjectant.

Résolvons \(39x – 24y = 15\). D’abord, \(39 \wedge 24 = 3\), qui divise 15. Après division par 3, l’équation devient \(13x – 8y = 5\). Le couple \((1, 1)\) convient, car \(13 – 8 = 5\). Par différence, une solution vérifie \(13(x – 1) = 8(y – 1)\). Ainsi, 8 divise \(13(x – 1)\) et \(8 \wedge 13 = 1\). Par Gauss, \(8 \mid x – 1\), soit \(x = 1 + 8k\). En reportant, \(13 \times 8k = 8(y – 1)\), d’où \(y = 1 + 13k\). Réciproquement, ces couples conviennent : \(13(1 + 8k) – 8(1 + 13k) = 5\).

Un entier \(p \geqslant 2\) est dit premier lorsqu’il n’a pas d’autre diviseur positif que 1 et lui-même. Leur ensemble est noté \(\mathcal{P}\).

Chaque entier \(n \geqslant 2\) est divisible par un nombre premier. Plus précisément, son plus petit diviseur \(d \geqslant 2\) est premier. Si \(n\) n’est pas premier, ce diviseur vérifie de plus \(d^2 \leqslant n\).

L’ensemble \(\mathcal{P}\) des nombres premiers est infini.

Raisonnons par l’absurde. Supposons que \(p_1, \dots, p_k\) soient tous les nombres premiers. Formons \(N = p_1 p_2 \cdots p_k + 1\), qui est au moins égal à 3. D’après le lemme, \(N\) possède un diviseur premier \(p\). Puisque la liste est complète, \(p\) est l’un des \(p_i\) ; il est donc facteur du produit \(p_1 \cdots p_k\). Étant aussi facteur de \(N\), il devrait diviser l’écart entre les deux, qui vaut 1. Un entier supérieur ou égal à 2 ne divise pas 1 : la supposition de départ tombe.

(Lemme d’Euclide.) Un nombre premier qui divise un produit \(ab\) divise forcément l’un des deux facteurs.

Tout entier \(n \geqslant 2\) s’écrit \(n = p_1^{\alpha_1} \cdots p_r^{\alpha_r}\), avec \(p_1 < \dots < p_r\) premiers et \(\alpha_i \geqslant 1\). Cette écriture est unique.

Pour l’existence, on raisonne par récurrence forte. Un nombre premier est sa propre décomposition. Un entier \(n\) composé s’écrit \(ab\) avec deux facteurs entre 2 et \(n – 1\) ; on décompose chacun d’eux, puis on réunit. Pour l’unicité, prenons deux écritures \(p_1 \cdots p_s = q_1 \cdots q_t\), où les facteurs sont répétés. Le facteur \(p_1\) est diviseur du membre de droite. En itérant le lemme d’Euclide, il est diviseur d’un certain \(q_j\), premier, donc \(p_1 = q_j\). On simplifie et l’on recommence. Les deux listes coïncident donc à l’ordre près.

Fixons un module \(n \geqslant 1\). L’écriture \(a \equiv b \pmod{n}\) signifie que la différence \(a – b\) est un multiple de \(n\). Cela revient à dire que la division par \(n\) laisse à \(a\) et à \(b\) le même reste.

Être congrus modulo \(n\) est réflexif, symétrique et transitif. Surtout, on peut additionner et multiplier membre à membre : si \(a \equiv a^{\prime}\) et \(b \equiv b^{\prime}\) modulo \(n\), alors \(a + b \equiv a^{\prime} + b^{\prime}\) et \(ab \equiv a^{\prime} b^{\prime}\). En particulier, \(a^k \equiv a^{\prime k}\) pour tout \(k \in \mathbf{N}\).

Pour le produit, on écrit \(ab – a^{\prime} b^{\prime} = a(b – b^{\prime}) + b^{\prime}(a – a^{\prime})\). Chaque terme est un multiple de \(n\), donc leur somme aussi. La règle des puissances s’obtient ensuite par récurrence sur \(k\).

L’entier \(a\) possède un inverse modulo \(n\), c’est-à-dire un \(u\) avec \(au \equiv 1 \pmod{n}\), exactement quand \(a\) et \(n\) sont premiers entre eux. Cet inverse est alors déterminé à un multiple de \(n\) près.

Résolvons \(7x \equiv 4 \pmod{30}\). D’abord, \(7 \times 13 = 91 = 3 \times 30 + 1\), donc 13 est un inverse de 7 modulo 30. Multiplions alors les deux membres par 13 : \(x \equiv 52 \equiv 22 \pmod{30}\). Vérification : \(7 \times 22 = 154 = 5 \times 30 + 4\). Les solutions sont donc les entiers \(22 + 30k\), \(k \in \mathbf{Z}\).

Quel que soit l’entier \(a\) et le nombre premier \(p\), la puissance \(a^p\) a le même reste que \(a\) modulo \(p\). Lorsque \(a\) n’est pas multiple de \(p\), on peut simplifier : \(a^{p-1}\) est alors congru à 1.

D’abord, pour \(1 \leqslant k \leqslant p – 1\), le nombre premier \(p\) divise \(\binom{p}{k}\). En effet, \(k \binom{p}{k} = p \binom{p-1}{k-1}\), donc \(p \mid k \binom{p}{k}\). Or \(p \wedge k = 1\), donc \(p \mid \binom{p}{k}\) par Gauss. La formule du binôme donne alors \((a + 1)^p \equiv a^p + 1 \pmod{p}\).

Ensuite, nous prouvons \(a^p \equiv a\) par récurrence pour \(a \in \mathbf{N}\). Le cas \(a = 0\) est clair. Si la propriété tient au rang \(a\), alors \((a+1)^p \equiv a^p + 1 \equiv a + 1\). Pour \(a\) négatif, on se ramène à un représentant positif de même reste. Enfin, si \(p \nmid a\), on simplifie \(a \cdot a^{p-1} \equiv a \cdot 1\) par \(a\), ce qui est permis car \(a \wedge p = 1\).

Pour calculer le reste de \(a^N\) modulo un nombre premier \(p\) ne divisant pas \(a\) :

1. on écrit la division euclidienne \(N = (p – 1) q + s\), avec \(0 \leqslant s < p – 1\) ;
2. on en déduit \(a^N = \left(a^{p-1}\right)^q a^s \equiv a^s \pmod{p}\) ;
3. on calcule \(a^s\) par carrés successifs, en réduisant modulo \(p\) à chaque étape.

Cherchons le reste de \(6^{1234}\) modulo 11. Le module 11 est premier et ne divise pas 6, donc \(6^{10} \equiv 1\). Or \(1234 = 10 \times 123 + 4\). Par conséquent, \(6^{1234} \equiv 6^4 \pmod{11}\). Ensuite, \(6^2 = 36 \equiv 3\), puis \(6^4 \equiv 3^2 = 9\). Le reste cherché vaut donc 9.

• S’exercer : exercices corrigés de L1 de maths sur divisibilité et congruences
• Bases utiles : Récurrence, symboles Σ et coefficients binomiaux
• Chapitre d’avant : Exponentielle, logarithme, fonctions arc et hyperboliques
• Chapitre d’après : Polynômes : division, racines et d'Alembert-Gauss
• Vérifier ses acquis : QCM de L1 de maths sur divisibilité et congruences
• Contrôle corrigé en temps limité : Algorithme d'Euclide et diophantiennes : contrôle de maths en L1
• Un autre sujet noté sur 20 : Partiel d'algèbre du premier semestre : contrôle de maths en L1
• Tous les chapitres : le sommaire de la L1 de maths
• Après le bac : les maths post-bac, de la MPSI à la L3