Chapitre 3
Cours 3
Congruences
Soient m un entier naturel non nul, et a et b deux entiers relatifs.
On dit que a et b sont congrus modulo m lorsqu'ils ont le même reste dans la division euclidienne par m.
On dit aussi que a est congru à b modulo m.
On note a≡b[m] ; a≡b(m) ou a≡bmodm.
15=2×7+1 et 21=2×10+1 donc 15≡21[2].
Soient m un entier naturel non nul et a et b deux entiers relatifs. a≡b[m] si, et seulement si, m∣(a−b).
En particulier, si a≡0[m], alors m ∣ a.
B
Congruences et opérations
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].
On dit que la relation de congruence est transitive.
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].
251≡8[3] et 8≡2[3] donc 251≡2[3].
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].
c≡c[m] donc, si a≡b[m], alors a+c≡b+c[m] et a×c≡b×c[m].
Il n'y a pas de compatibilité avec la division : 62≡26[4] mais 31 et 13 ne sont pas congrus modulo 4.
Application et méthode - 5
Montrer en utilisant un tableau de congruence que, pour tout entier relatif n, n(n+1)(2n+1) est divisible par 3.
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.
On dresse un tableau de congruence de
n modulo 3.
n≡…[3] | 0 | 1 | 2 |
(n+1)≡…[3] | 1 | 2 | 3≡0 |
(2n+1)≡…[3] | 1 | 3≡0 | 5≡2 |
Produit
n(n+1)(2n+1)≡…[3] | 0×1×1≡0 | 1×2×0≡0 | 2×0×2≡0 |
On remarque que, pour tout entier
n,
n(n+1)(2n+1)≡0[3], c'est‑à‑dire que
n(n+1)(2n+1) est divisible par
3.
Pour s'entraîner
Exercices
et
.
Soient a un entier relatif et m un entier naturel non nul.
On dit que a est inversible modulo m lorsqu'il existe un entier b tel que a×b≡1[m].
8 est inversible modulo 3 car 8×2≡1[3]. 2 est donc un inverse de 8 modulo 2.
Application et méthode - 6
1. Démontrer que 3 est inversible modulo 5.
2. Montrer que 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.
1. Soit
b un entier relatif. On établit un tableau de congruence modulo
5.
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.
Pour s'entraîner
Exercices
et
p. 105.
Une erreur sur la page ? Une idée à proposer ?
Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.