Congruences en maths expertes : calculer modulo n sans jamais diviser

Les congruences portent toute la partie arithmétique de l'option maths expertes de terminale. Le programme (BO spécial n° 8 du 25 juillet 2019) les place juste après la division euclidienne, avec une capacité précise : résoudre une congruence ax ≡ b [n] et trouver un inverse de a modulo n.

a ≡ b [n] : même reste, ou différence multiple de n

Division euclidienne. Pour tout a ∈ ℤ et tout n ∈ ℕ*, il existe un unique couple (q ; r) d'entiers tel que a = nq + r et 0 ≤ r < n. Le reste est toujours positif, même quand a est négatif : −17 = 5 × (−4) + 3, donc le reste de −17 par 5 est 3, et non −2.

Définition. a ≡ b [n] signifie que n divise a − b, c'est-à-dire qu'il existe k ∈ ℤ tel que a = b + kn.

Propriété. a ≡ b [n] si et seulement si a et b ont le même reste dans la division par n. Si a = nq + r et b = nq′ + r, alors a − b = n(q − q′). Réciproquement, si a − b = nk et a = nq + r avec 0 ≤ r < n, alors b = n(q − k) + r, et par unicité de la division euclidienne r est aussi le reste de b.

Conséquence pratique : tout entier est congru modulo n à son reste, qui est l'un des n nombres 0, 1, …, n − 1. Un raisonnement « pour tout entier a » modulo n se ramène donc à n cas.

Ce qu'on a le droit de faire, et ce qui est interdit

Compatibilité avec les opérations. Si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n], a − c ≡ b − d [n] et ac ≡ bd [n]. Par récurrence, aᵏ ≡ bᵏ [n] pour tout k ∈ ℕ.

Pour la somme, (a + c) − (b + d) = (a − b) + (c − d) est une somme de deux multiples de n. Pour le produit, on écrit ac − bd = a(c − d) + d(a − b) : chaque terme est un multiple de n, donc la somme aussi. Pour les puissances, si aᵏ ≡ bᵏ [n], on multiplie membre à membre par a ≡ b [n] et l'on obtient aᵏ⁺¹ ≡ bᵏ⁺¹ [n].

Deux gestes ne sont pas permis. On ne divise pas : 2 × 3 ≡ 2 × 1 [4] puisque 6 − 2 = 4, et pourtant 3 n'est pas congru à 1 modulo 4. On ne réduit pas un exposant modulo n : 100 ≡ 2 [7], mais 2¹⁰⁰ n'est pas congru à 2² modulo 7, comme le montre l'exemple qui suit.

Le reste d'une grande puissance

La méthode tient en trois temps. On calcule les restes des premières puissances jusqu'à retomber sur 1. On écrit l'exposant sous la forme (longueur du cycle) × q + r. On conclut avec la compatibilité avec les puissances. Je demande de rédiger la ligne « donc (aᵐ)^q ≡ 1^q [n] » : c'est elle que le correcteur cherche.

Exemple 1 · Le reste de 2¹⁰⁰ dans la division par 7

Rédaction. 2⁰ = 1, 2¹ = 2, 2² = 4 et 2³ = 8 ≡ 1 [7]. Or 100 = 3 × 33 + 1, donc 2¹⁰⁰ = (2³)³³ × 2. Comme 2³ ≡ 1 [7], on a (2³)³³ ≡ 1³³ = 1 [7], puis 2¹⁰⁰ ≡ 2 [7]. Comme 0 ≤ 2 < 7, le reste de 2¹⁰⁰ par 7 est 2.

L'élève qui « réduit » l'exposant, 100 ≡ 2 [7] donc 2¹⁰⁰ ≡ 2² = 4, trouve 4 : c'est faux. L'exposant se réduit modulo la longueur du cycle, ici 3, jamais modulo 7.

Quand le module p est premier, le petit théorème de Fermat donne un cycle sans rien chercher : 3 n'est pas divisible par 7, donc 3⁶ ≡ 1 [7]. Avec 100 = 6 × 16 + 4, on obtient 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 [7]. Le cycle réel peut être plus court que p − 1, comme pour 2 modulo 7, de longueur 3.

La figure suit cet exemple. Les sept restes modulo 7 sont d'abord posés sur un cercle, comme les heures d'une horloge. Le reste de 2⁰ s'allume sur 1, puis une flèche mène à 2 pour 2¹, une autre à 4 pour 2², et la troisième revient sur 1 pour 2³ = 8 : le cycle est bouclé en trois pas. La dernière étape écrit 100 = 3 × 33 + 1 et lit le résultat, 2¹⁰⁰ ≡ 2 [7].

Les critères de divisibilité, démontrés

Le programme demande d'établir des tests de divisibilité. Tous reposent sur une congruence de 10.

Exemple 2 · Le critère de divisibilité par 9

Énoncé. Montrer qu'un entier naturel est congru modulo 9 à la somme de ses chiffres. En déduire que 4 752 est divisible par 9 et donner le reste de 8 137 par 9.

Rédaction. Écrivons n = aₖ × 10ᵏ + … + a₁ × 10 + a₀, où a₀, …, aₖ sont les chiffres de n. Comme 10 ≡ 1 [9], on a 10ⁱ ≡ 1 [9] pour tout i ∈ ℕ, donc aᵢ × 10ⁱ ≡ aᵢ [9], et en additionnant n ≡ aₖ + … + a₁ + a₀ [9].

4 + 7 + 5 + 2 = 18 ≡ 0 [9], donc 4 752 est divisible par 9 (4 752 = 9 × 528). 8 + 1 + 3 + 7 = 19 ≡ 1 [9], donc le reste de 8 137 par 9 est 1. Le même raisonnement avec 10 ≡ 1 [3] donne le critère de divisibilité par 3, et 10 ≡ −1 [11] celui par 11, avec une somme alternée des chiffres.

Résoudre ax ≡ b [n]

On cherche un inverse de a modulo n, un entier u tel que au ≡ 1 [n], en essayant les valeurs de 1 à n − 1 ou avec un couple de Bézout. On multiplie les deux membres par u, ce qui donne x ≡ ub [n]. Puis on vérifie la réciproque en multipliant par a. L'inverse existe exactement quand a et n sont premiers entre eux : au + nv = 1 est une égalité de Bézout.

Exemple 3 · Résoudre 3x ≡ 5 [7] dans ℤ

Rédaction. 3 × 5 = 15 = 2 × 7 + 1, donc 3 × 5 ≡ 1 [7] : 5 est un inverse de 3 modulo 7. Si 3x ≡ 5 [7], en multipliant par 5 : 15x ≡ 25 [7], soit x ≡ 4 [7]. Réciproquement, si x ≡ 4 [7], alors 3x ≡ 12 ≡ 5 [7]. Les solutions sont les entiers x = 4 + 7k, k ∈ ℤ.

Si a et n ne sont pas premiers entre eux, la méthode tombe. L'équation 2x ≡ 2 [4] a deux familles de solutions, x ≡ 1 [4] et x ≡ 3 [4] (2 × 3 = 6 ≡ 2 [4]) : « simplifier par 2 » en perd une. L'équation 2x ≡ 3 [4] n'en a aucune, puisque 2x − 3 est impair et ne peut pas être multiple de 4. Dans ces cas, on teste les n restes possibles un par un.

Cinq fautes qui coûtent des points modulo n

• Un reste négatif : « −17 ≡ −2 [5], donc le reste est −2 ». La congruence est vraie, la conclusion est fausse.
• L'exposant réduit modulo n au lieu de la longueur du cycle.
• Une division par un nombre non premier avec n, qui fait perdre des solutions.
• Une congruence sans son modulo, « 2³ ≡ 1 », qui ne veut rien dire.
• La réciproque oubliée après la multiplication par l'inverse.

Trois exercices corrigés sur les congruences

Exercice 1 · n³ − n est toujours multiple de 3

Énoncé. Montrer que pour tout entier relatif n, n³ − n est divisible par 3.

Correction. Tout entier est congru à 0, 1 ou 2 modulo 3. Si n ≡ 0 [3], n³ − n ≡ 0 − 0 = 0 [3]. Si n ≡ 1 [3], n³ − n ≡ 1 − 1 = 0 [3]. Si n ≡ 2 [3], n³ − n ≡ 8 − 2 = 6 ≡ 0 [3]. Dans les trois cas, 3 divise n³ − n. La factorisation n³ − n = (n − 1)n(n + 1), produit de trois entiers consécutifs, en donne une seconde preuve.

Exercice 2 · Un inverse modulo 12

Énoncé. Résoudre dans ℤ l'équation 7x ≡ 3 [12].

Correction. 7 × 7 = 49 = 4 × 12 + 1, donc 7 est son propre inverse modulo 12. Si 7x ≡ 3 [12], en multipliant par 7 : 49x ≡ 21 [12], soit x ≡ 9 [12]. Réciproquement, 7 × 9 = 63 = 5 × 12 + 3, donc 7 × 9 ≡ 3 [12]. Les solutions sont les entiers x = 9 + 12k, k ∈ ℤ.

Exercice 3 · Une somme de puissances divisible par 7 pour tout n

Énoncé. Montrer que pour tout n ∈ ℕ, 3²ⁿ⁺¹ + 2ⁿ⁺² est divisible par 7.

Correction. 3²ⁿ⁺¹ = 3 × 9ⁿ et 9 ≡ 2 [7], donc 3²ⁿ⁺¹ ≡ 3 × 2ⁿ [7]. De plus 2ⁿ⁺² = 4 × 2ⁿ. Ainsi 3²ⁿ⁺¹ + 2ⁿ⁺² ≡ 3 × 2ⁿ + 4 × 2ⁿ = 7 × 2ⁿ ≡ 0 [7]. Contrôle : pour n = 0, 3 + 4 = 7 ; pour n = 1, 27 + 8 = 35 = 7 × 5. Une récurrence marche aussi, mais elle est plus longue.