Dans cet article, nous allons vous présenter la notion de congruence, indispensable pour gagner du temps dans les démonstrations en arithmétique
Prérequis
Définition
Soient a et b deux entiers relatifs. Soit n\geq 2 un entier naturel. Les deux définitions suivants sont équivalentes :
- a et b sont congrus modulo n si et seulement si leur différence est divisible par n, c’est à dire qu’il existe k entier relatif tel que a-b = kn
- a et b sont congrus modulo n si le reste de la division euclidienne de a par n est égal à celui de la division euclidienne de b par n.
On peut noter “a congru à b modulo n” des manières suivantes :
- a \equiv b [n]
- a = b(\mod n)
Propriétés
La relation de congruence est une relation d’équivalence. On en tire donc 3 premières propriétés :
- a \equiv a[n]
- a \equiv b[n]\iff b \equiv a[n]
- Si a \equiv b[n] et b \equiv c[n] alors a \equiv c[n]
Voici quelques propriétés importantes de la congruence. Si a, b, c et d sont 4 entiers relatifs tels que a \equiv b [n] et c \equiv d[n] , alors :
- - a \equiv -b[n]
- a +c\equiv b +d[n]
- ac \equiv bd [n]
- \forall k \in \N, a^k \equiv b^k [n]
Exemples
- 7 et 16 sont congrus modulo 3 car 16 - 7 = 3 \times 3
- 7 et 11 ne sont pas congrus modulo car le reste de la division euclidienne de 7 par 5 est 2 tandis que le reste de la division euclidienne de 11 par 5 est 1.
Exercices corrigés
Exercice 1
Enoncé : Quel est le dernier chiffre de 3^{2022} ?
Corrigé : On regarder les puissance de 3 modulo 10 :
- 3^1 \equiv 3 [10]
- 3^2 \equiv 9 [10]
- 3^3 \equiv 27 \equiv 7 [10]
- 3^4 \equiv 21 \equiv 1 [10]
Donc on a un cycle de longueur 4 : toutes les 4 puissances, le dernier chiffre est 1, le cycle se répète. On sait donc que 3^{4k}\equiv 1 [10] .
Regardons alors 2022 modulo 4, grâce à la division euclidienne. 2022 = 505 \times 4 + 2 . On a alors :
\begin{array}{ll}
3^{2022} &= 3^{4\times 505} 3^2\\
&= (3^4)^{505} 3^2\\
& \equiv 1^{505}3^2 [10]\\
& \equiv 9 [10]
\end{array}Le dernier chiffre est donc 9.
Exercice 2
Enoncé : Démontrer que la somme de trois cubes consécutifs est toujours divisible par 9.
Corrigé : Notons n le premier cube consécutif. On considère donc la somme n^3 + (n+1)^3 + (n+2)^3 . Développons cette somme :
\begin{array}{ll}
&n^3 + (n+1)^3 + (n+2)^3 \\
=& n^3 + n^3 + 3n^2 +3n + 1+ n^3 + 6n^2+ 12n + 8\\
=& 3n^3 + 9n^2 + 15n + 9
\end{array}Il est clair que 9n^2+ 9 \equiv 0 [9] . Maintenant, on remarque que 3n^3 + 15 n =3n (n^2 +5).
Comme on a déjà un 3 en facteur, il suffit de montrer que n(n^2 +5) \equiv 0 [3]. Or, si n \equiv 0 [3] c’est gagné. Si n \equiv 1 [3] ou n \equiv 2 [3] alors n ^2 \equiv 1 [3] et donc n^2 +5 \equiv 0 [3]. D’où n(n^2+5) \equiv 0 [3] dans tous les cas. Donc,
3n^3 + 15 n \equiv 0 [9]
Ce qui suffit pour conclure.
Exercice 3
Enoncé : Démontrer que 13 divise 3^{126}+5^{126}
Corrigé : Calculons les puissance de 3 modulo 13 :
- 3^1 \equiv 3 [13]
- 3^2 \equiv 9 [13]
- 3^3 \equiv 1 [13]
On fait donc la division euclidienne de 126 par 3 : 126 = 3 \times 42 . On a donc 3^{126} = (3^3)^{42} \equiv 1 [13].
Faisons le même travail avec 5 :
- 5^1 \equiv 5 [13]
- 5^2 \equiv 12 [13]
- 5^3 \equiv 8 [13]
- 5^4 \equiv 1 [13]
On va donc faire la division euclidienne de 126 par 4 : 126 = 31 \times 4 + 2 .
On a ainsi 5^126 = (5^4)^{31}\times 5^2 \equiv 1^31 \times 12 [13] .
Ainsi, 3^{126} + 5^{126} \equiv 1+ 12 \equiv 0 [13] ce qui est bien le résultat recherché.
Exercice 4 (en vidéo)
Voici un corrigé en vidéo utilisant des congruences :
