Congruences
Définition
On dit que a et b sont congrus modulo n signifie que a et b ont le même reste dans la division euclidienne par n.
On note a\equiv b[n] ou a\equiv b(modn)
Exemple n°1 :
92 et 106 sont congrus modulo 7 car 92 et 106 ont le même reste : 1 dans la division euclidienne par 7.
On note 92\equiv 106[7]
Illustration avec la TI 83 Premium CE Python :
Exemple n°2 :
452 et 27 sont congrus modulo 5 car 452 et 27 ont le même reste : 2 dans la division euclidienne par 5.
On note 452\equiv 27[5]
Illustration avec la TI 83 Premium CE Python :
Conséquences
a\equiv a[n]si a\equiv b[n] alors b\equiv a[n]
si a\equiv b[n] et b\equiv c[n] alors a\equiv c[n].
si r est le reste de la division de a par b alors a \equiv r[n].
a\equiv 0[n] si et seulement si a est divisible par a.
Propriété
a\equiv b[n] si et seulement si a-b est un multiple de n.
Démonstration
Si a\equiv b[n] alors il existe des entiers relatifs q , q’ et r tels que a=nq+r et b=nq’+r avec 0\leq r<n.
On soustrait les deux égalités :
a-b=nq+r-nq’-r\\a-b=nq-nq’\\a-b=n(q-q’) donc a-b est un multiple de n.
Réciproquement, si a-b est un multiple de n alors il existe un entier relatif k tel que a-b=kn ou a=b+kn.
Si on divise b par n, on obtient b=n\times q’+r’ avec 0\leq r'<n.
On remplace b par n\times q’+r’ dans a=b+kn.
a=n\times q’+r’+kn
a=n(q’+k)+r’ avec 0\leq r'<n.
Donc r’ est aussi le reste de la division de a par n.
Donc a et b ont le même reste r’ dans leur division par n.
Donc a\equiv b[n].
Propriétés
Si a\equiv b[n] et c\equiv d[n] alors :
a+c\equiv b+d[n]\\a-c\equiv b-d[n]\\ac\equiv bd[n]Pout tout p\in \mathbf{N} , a^p\equiv b^p[n]
Exemple n°3 :
a et b sont deux entiers tels que a\equiv7[13] et b\equiv4[13]
- Donner le reste de la division euclidienne par 13 de a+b.
On utilise la propriété Si a\equiv b[n] et c\equiv d[n] alors a+c\equiv b+d[n].
a\equiv7[13] et b\equiv4[13] donc a+b\equiv7+4[13]\\a+b\equiv11[13], comme 0\leq 11<13, le reste de la division de a+b par 13 est 11.
2.Donner le reste de la division euclidienne par 13 de a-b.
On utilise la propriété Si a\equiv b[n] et c\equiv d[n] alors a-c\equiv b-d[n].
a\equiv7[13] et b\equiv4[13] donc a-b\equiv7-4[13]\\a-b\equiv 3[13], comme 0\leq 3<13, le reste de la division de a-b par 13 est 3.
3.Donner le reste de la division euclidienne par 13 de ab.
On utilise la propriété Si a\equiv b[n] et c\equiv d[n] alors ac\equiv bd[n].
a\equiv7[13] et b\equiv4[13] donc ab\equiv7\times4[13]\\ab\equiv 28[13], comme 28>13, il faut diviser 28 par 13.
28=2\times 13+2 donc le reste de la division de 28 par 13 est 2.
Comme ab\equiv 28[13], ils ont même reste dans la division par 13, donc le reste de la division de ab par 13 est 2
4.Donner le reste de la division euclidienne par 13 de a^2.
On utilise la propriété Si a\equiv b[n] alors a^2\equiv b^2[n].
a\equiv7[13] donc a^2\equiv7^2[13]\\a^2\equiv 49[13], comme 49>13, il faut diviser 49 par 13.
49=3\times 13+10 donc le reste de la division de 49 par 13 est 10.
Comme a^2\equiv 28[13], ils ont même reste dans la division par 13, donc le reste de la division de a^2 par 13 est 10
Exemple n°4 : tableau de congruence
- Reproduire et compléter (en rouge) le tableau de congruence modulo 3 ci-dessous où n représente un entier relatif.
| n\equiv…[3] | n\equiv 0 | n\equiv 1 | n\equiv 2[3] |
| n^2\equiv…[3] | n^2\equiv0[3] | n^2\equiv 1[3] | n^2\equiv 4[3] |
| 2n\equiv…[3] | 2n\equiv0[3] | 2n\equiv 2[3] | 2n\equiv 4[3] |
| n^2+2n\equiv…[3] | n^2+2n\equiv0[3] | n^2+2n\equiv 3[3] | n^2+2n\equiv8[3] |
2. Déterminer alors les restes de la division de n^2+2n par 3.
Compte-tenu de la dernière ligne du tableau, on constate que les restes seront : 0 ou 2.
En effet on a n^2+2n\equiv 3[3] et 3\equiv 0[3] donc n^2+2n\equiv 0[3].
Et on a n^2+2n\equiv 8[3] et 8\equiv 2[3] donc n^2+2n\equiv 2[3].
Exercice n°1
a et b sont deux entiers tels que a\equiv 6[11] et b\equiv 4[11]
- Donner le reste de la division euclidienne par 11 de a+b.
2. Donner le reste de la division euclidienne par 11 de a-b.
3. Donner le reste de la division euclidienne par 11 de ab.
4. Donner le reste de la division euclidienne par 11 de 5a.
5. Donner le reste de la division euclidienne par 11 de a^3.
Exercice n°2
a et b sont deux entiers tels que a\equiv 2[7] et b\equiv 5[7]
- Donner le reste de la division euclidienne par 7 de a+b.
2. Donner le reste de la division euclidienne par 7 de a-b.
3. Donner le reste de la division euclidienne par 7 de ab.
4. Donner le reste de la division euclidienne par 7 de 4a.
5. Donner le reste de la division euclidienne par 7 de a^3.
Exercice n°3
- x désigne un nombre entier relatif, démontrer que si x n’est pas un multiple de 3 , alors x^2\equiv 1[3].
2. Démontrer que pour tous entiers relatifs a et b , le nombre N=ab(a^2-b^2) est divisible par 3
Exercice n°4
- Démontrer que 5^2\equiv -1[13] puis que 5^4\equiv 1[13]
2. n désigne un nombre entier naturel, démontrer que 5^{4n}\equiv 1[13].
Exercice n°5
Déterminer le reste de la division par 7 de 78^{115}+92^{23}+106^{35}.
Exercice n°6
On donne A=877+59^{43} . On souhaite déterminer le reste de la division euclidienne de A par 7.
- Justifier que 59\equiv 3[7] et que 3^6\equiv 1[7].
2. Effectuer la division de 43 par 6 et en déduire que 3^{43}\equiv 3[7].
3. Quel est finalement le reste cherché ?.
Exercice n°7
n désigne un nombre entier naturel.
Déterminer les restes de la division euclidienne de :
Exercice n°8 :
A l’aide d’un tableau de congruences et de la calculatrice, démontrer que pour tout nombre entier naturel n,
n^7+6n\equiv0[7].
