Congruence : Cours et exercices corrigés

Voici un cours avec des exercices corrigés sur le thème des congruences
Congruence

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 :

Total
0
Partages

Laisser un commentaire

Articles similaires