Utilisation de la congruence dans les démonstrations.

Test 1 : Déterminer le chiffre des unités du nombre 2¹⁰⁰⁰.
Le chiffre des unités est le résultat de la congruence modulo 10. En écrivant les premières puissances de 2 on obtient 2 ; 4 ; 8 ; 16 ; 32 ; ... On remarque alors que 32 = 2⁵ et 32 ≡ 2 [10] donc 2⁵ ≡ 2 [10].
2¹⁰⁰⁰ = 2^5×200 =(2⁵)²⁰⁰ ≡ 2²⁰⁰ [10]. Mais on peut écrire 2²⁰⁰ = 2^5×40 (2⁵)⁴⁰ ≡ 2⁴⁰ [10].
Finallement, 2⁴⁰ = 2^5×8 = (2⁵)⁸ ≡ 2⁸ [10]. Or 2⁸ = 2⁵⁺³ = 2⁵×2³ ≡ 2×2³ [10] soit 2⁴ = 16.
Par conséquent, 2¹⁰⁰⁰ ≡ 6 [10]. Le chiffre des unités du nombre 2¹⁰⁰⁰ est 6.

En utilisant une console Python, on obtient :
>>> 2**1000
1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378
8156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074
6050623711418779541821530464749835819412673987675591655439460770629145711964776865421676604
29831652624386837205668069376
>>>
Le dernier chiffre est bien 6 !

Par une méthode semblable modulo 100, on peut arriver à déterminer les deux derniers chiffres d'un nombre donné...
2¹⁰ = 1024 ≡ 24 [100] et 24² = 576 ≡ 76 [100] ≡ -24 [100]. De plus (24²)² = ≡ (-24)² [100] (compatibilité avec les puissances).
On retombe sur (-24)² = 24² ≡ -24 [100]. Ainsi les puissances paires de 24 sont congrues à -24 soit 76 modulo 100.
Par conséquent 2¹⁰⁰⁰ =(2¹⁰)¹⁰⁰ ≡ 24¹⁰⁰ [100] et comme 100 est pair, 24¹⁰⁰ ≡ 76 [100].
Les deux derniers chiffres de 2¹⁰⁰⁰ sont 7 et 6 respectivement chiffre des dizaines et chiffre des unités.

Test 2 : Déterminer un critère de divisibilité par 17.
On isole le chiffre des unités en écrivant le nombre n = A + 10×B.
On a 10 ≡ -7 [17] donc A + 10×B ≡ A -7×B [17] (compatibilité de la congruence avec multiplication et addition).
Si A -7B est divisible par 17 le nombre de départ l'est aussi. Toutefois cette "formule" n'est pas très facile à utiliser...
L'astuce est de la multiplier par un nombre de sorte à ramener le coefficient de B à 1 (modulo 17).
On remarque que 17×2 = 34 et 7×5 = 35 ≡ 1 [17]. En multipliant par -5 on arrive alors à n ≡ B - 5×A [17].
Si le nombre ainsi obtenu est divisible par 17 n sera divisible par 17.
n = 1904 = 190×10 + 4 d'où A = 4 et B = 190. B - 5×A = 190 - 5×4 = 170 (divisible par 17). En effet, 1904 = 17 × 112.

En procédant de la même manière on arrive aux critères de divisbilité suivants :
Le nombre initial est toujours noté n = A + 10×B.
Divisibilité par 7 : B - 2A divisible par 7.
Divisibilité par 13 : B + 4A divisible par 13.
ex : n = 1547. 154 + 4×7 = 154 + 28 = 182. Si le multiple de 13 n'est pas évident, on recommence l'opération.
18 + 4×2 = 18 + 8 = 26 = 2×13. Donc 182 et également 1547 sont divisibles par 13.

Test 3 : Déterminer le reste d'une division euclidienne (d'après BAC S 2009).
1. Démontrer que pour tout nombre entier naturel k on a : 2^3k ≡ 1 [7].
On a 2³ = 8 et 8 ≡ 1 [7]. Par compatibilité de la congrence avec les puissances 2^3k = (2³)^k = 8^k et 8^k ≡ 1^k [7].
Par conséquent 2^3k ≡ 1 [7].
2. Quel est le reste dans la division euclidienne de 2²⁰⁰⁹ par 7 ?
On a 2009 = 3×669 + 2. Ainsi 2²⁰⁰⁹ = 2^3×669+2 = 2^3×669×2². On a 2^3×669 ≡ 1 [7] donc 2²⁰⁰⁹ ≡ 4 [7]

En utilisant une console Python, on obtient :

>>> 2**2009 % 7 4 >>>

Test 4 : Démontrer que pour tout entier naturel n, n(n² + 5) est divisible par 6.
Dans ce type d'excercice on raisonne par disjonctiondes cas. Le reste de la division euclidienne d'un nombre par 6 est 0, 1, 2, 3, 4 ou 5.
On présente cela dans un tableau de congruence. On peut mettre des étapes intermédiaires pour éviter les erreurs...

n ≡ ...[6] 0 1 2 3 4 5 n2 ≡ ...[6] 0 1 4 3 4 1 n2 + 5 ≡ ...[6] 5 0 3 2 3 0 n(n2 + 5) ≡ ...[6] 0 0 0 0 0 0

La dernière ligne de ce tableau montre que quel que soit le nombre de départ le reste de la division par 6 est 0. Par conséquent, pour tout n ∈ ℕ, n(n2 + 5) est divisible par 6.

Remarque : On pourrait également montrer que pour tout entier n, 2 divise n(n² + 5) et 3 divise n(n² + 5).
Sachant que 2 et 3 sont premiers entre eux, d'après le corollaire du théorème de Gauss, 2×3 = 6 divise n(n² + 5).

Test 5 : Démontrer l'équivalence suivante : n ≡ 9 [17] ⇔ PGCD(9n + 4, 2n - 1) = 17.
Pour démontrer une équivalence A ⇔ B, on démontre que A ⇒ B et sa réciproque B ⇒ A.
• Si n ≡ 9 [17] alors il existe un entier relatif k tel que n = 17×k + 9.
Ainsi on a : 9n + 4 = 9×(17×k + 9) + 4 = 9×17k + 85 = 17×(9k + 5) et 2n - 1 = 2×(17×k + 9) - 1 = 2×17k + 17 = 17×(2k + 1)
Par conséquent :
PGCD(9n + 4, 2n - 1) = PGCD(17×(9k + 5), 17×(2k + 1)) = 17×PGCD(9k + 5, 2k + 1) (Homogénéité du PGCD)
Or 2×(9k + 5) - 9×(2k + 1) = 1. D'après le théorème de Bézout pour tout entier relatif k, 9k + 5 et 2k + 1 sont premiers entre eux.
Donc PGCD(9k + 5, 2k + 1) = 1, et par conséquent : PGCD(9n + 4, 2n - 1) = 17×1 = 17.
Réciproquement :
• Si PGCD(9n + 4, 2n - 1) = 17 alors 17 divise 9n + 4, 17 divise 2n - 1 et toutes combinaison linéaires de 9n + 4 et 2n - 1.
En particulier, 1×(9n + 4) - 4×(2n - 1) = 9n + 4 - 8 n + 4 = n + 8. Donc 17 divise n + 8.
Ainsi on peut écrire : n + 8 ≡ 0 [17], soit encore n ≡ - 8 [17]. D'où n ≡ 9 [17] (car - 8 + 17 = 9).
• Finalement on a démontré que :
n ≡ 9 [17] ⇒ PGCD(9n + 4, 2n - 1) = 17 et PGCD(9n + 4, 2n - 1) = 17 ⇒ n ≡ 9 [17]
donc n ≡ 9 [17] ⇔ PGCD(9n + 4, 2n - 1) = 17