Soient m un entier naturel non nul, et a et b deux entiers relatifs.
On dit que a et b sont congrus modulom lorsqu’ils ont le même reste dans la division euclidienne par m.
On dit aussi que a est congru à b modulo m.
NOTATION
On note a≡b[m] ; a≡b(m) ou a≡bmodm.
Exemple
15=2×7+1 et 21=2×10+1 donc 15≡21[2].
Théorème
Soient m un entier naturel non nul et a et b deux entiers relatifs. a≡b[m] si, et seulement si, m∣(a−b).
Soient a, b et c trois entiers relatifs et m un entier naturel non nul.
Si a≡b[m] et b≡c[m], alors a≡c[m].
Remarque
On dit que la relation de congruence est transitive.
DÉMONSTRATION
D’après les hypothèses, a et b ont le même reste dans la division euclidienne par m, et b et c ont le même reste dans la division euclidienne par m, donc a et c ont le même reste dans la division euclidienne par m donc a≡c[m].
Exemple
251≡8[3] et 8≡2[3] donc 251≡2[3].
Propriétés
Soient a, b, c et d quatre entiers relatifs et m un entier naturel non nul. 1. Compatibilité avec l'addition
Si a≡b[m] et c≡d[m], alors a+c≡b+d[m].
2. Compatibilité avec la multiplication
Si a≡b[m] et c≡d[m], alors a×c≡b×d[m].
3. Compatibilité avec les puissances
Soit p un entier naturel non nul. Si a≡b[m], alors ap≡bp[m].
Cas particuliers
c≡c[m] donc, si a≡b[m], alors a+c≡b+c[m] et a×c≡b×c[m].
ATTENTION
Il n’y a pas de compatibilité avec la division : 62≡26[4] mais 31 et 13 ne sont pas congrus modulo 4.
On recherche les restes possibles de n dans la division par 3 (conséquence de la division euclidienne).
On complète le tableau de congruence pour obtenir, dans la dernière ligne, les restes possibles de la division de n(n+1)(2n+1) par 3. Ces restes étant toujours nuls, on en déduit que, pour tout entier n, n(n+1)(2n+1) est divisible par 3.
C
Inverse modulo m
Définition
Soient a un entier relatif et m un entier naturel non nul.
On dit que a est inversible modulom lorsqu’il existe un entier b tel que a×b≡1[m].
Exemple
8 est inversible modulo 3 car 8×2≡1[3]. 2 est donc un inverse de 8 modulo 2.
Application et méthode - 6
Énoncé
1. Démontrer que 3 est inversible modulo 5. 2. Montrer que 4 n’admet pas d’inverse modulo 6.
Solution
1. Soit b un entier relatif. On établit un tableau de congruence modulo 5.
b≡…[5]
0
1
2
3
4
3b≡…[5]
0
3
1
4
2
On a donc 3×2≡1[5] donc 2 est un inverse de 3 modulo 5.
Cet inverse n’est d’ailleurs pas unique : tout entier s’écrivant 5k+2, avec k∈Z, est un inverse de 3 modulo 5.
2. Soit c un entier relatif. On établit un tableau de congruence modulo 6.
c≡…[6]
0
1
2
3
4
5
4c≡…[6]
0
4
2
0
4
2
Il n’existe pas d’entier c tel que 4c≡1[6] Donc 4 n’admet pas d’inverse modulo 6.
1. On recherche un entier b tel que 3b≡1[5].
Pour cela, on établit un tableau de congruence modulo 5, en recherchant les restes possibles de 3b modulo 5. Dans le tableau, on recherche s’il existe un entier b tel que 3b≡1[5]. Dans ce cas, on observe que l’entier 2 est une solution.
2. On établit un tableau de congruence modulo 6. On observe que 4c n’est jamais congru à 1 modulo 6.
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service. Pour plus d’informations, cliquez ici.