"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre l • Arithmétique
12
Quel que soit a entier, a= a [ n] et a= r [ n] , r étant le reste de la division euclidienne de a par n.
Exemples
l 01 = 7 X 14 + 3 et 66 = 7 X 9 + 3
donc l 01 et 66 sont congrus modulo 7 car ils ont le même reste dans les divisions
euclidiennes par 7. On peut donc écrire l 01 = 66 [7].
67 = 12 X 5 + 7 et 139 = 12 X l l + 7
donc 67 = 139 [l 2] car le reste est le même dans les divisions euclidiennes par 12.
29 = 8 x 3 + 5 donc 29 = 5 [8].
90 et 80 ne sont pas congrus modulo 11, car les restes dans les divisions euclidiennes par l l sont 2 et 3.
Propriété 1.6
Soit a et b deux entiers naturels tels que a > b et soit n un entier naturel non nul.
a est congru à b modulo n si et seulement si a - b est multiple de n.
En effet, si a = b [ n] alors a et b ont le même reste r dans la division euclidienne
par n.
Donc on a a =nq+r et b=nq'+r puis a-b=(nq+r)-(nq'+r)=nq-nq'
= n( q - q ') qui est un multiple de n puisque q-q' est un entier.
Propriété 1. 7
Soit a, b, c, d des entiers naturels et n un entier naturel non nul.
Si a = b [ n] et c = d [ n] alors :
- a+ c = b + d [ n] et a - c = b - d[n]
- pa = pb [ n] pour tout entier naturel p
- ac = bd[n]
- aP = bP [ n] pour tout entier naturel p
Des démonstrations de certaines de ces propriétés sont proposées dans l' exercice
corrigé 1.45.
Exemples
À partir des congruences 2 014 = l [3] et 1 000 = l [3], les propriétés précédentes
permettent d'obtenir facilement d'autres congruences :
2 014 + l 000 = l + l [3] c'est-à-dire 3014 = 2[3]
20 x 2 014 = 20 x l [3] c'est-à-dire 40 280 = 20[3] donc 40 280 = 2[3]
2 014 x l 000 = l x l [3] c'est-à-dire 2 014 000 = l [3]
2 014
70
= 1
70 [3] c'est-à-dire 2 014
70
= l [3] (sur cet exemple , on vient de montrer
très facil ement que le re ste de la division euclidienne de 2 014
70 par 3 est l, ce
qui n'avait rien d'évident ... ).
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre l • Arithmétique
12
Quel que soit a entier, a= a [ n] et a= r [ n] , r étant le reste de la division euclidienne de a par n.
Exemples
l 01 = 7 X 14 + 3 et 66 = 7 X 9 + 3
donc l 01 et 66 sont congrus modulo 7 car ils ont le même reste dans les divisions
euclidiennes par 7. On peut donc écrire l 01 = 66 [7].
67 = 12 X 5 + 7 et 139 = 12 X l l + 7
donc 67 = 139 [l 2] car le reste est le même dans les divisions euclidiennes par 12.
29 = 8 x 3 + 5 donc 29 = 5 [8].
90 et 80 ne sont pas congrus modulo 11, car les restes dans les divisions euclidiennes par l l sont 2 et 3.
Propriété 1.6
Soit a et b deux entiers naturels tels que a > b et soit n un entier naturel non nul.
a est congru à b modulo n si et seulement si a - b est multiple de n.
En effet, si a = b [ n] alors a et b ont le même reste r dans la division euclidienne
par n.
Donc on a a =nq+r et b=nq'+r puis a-b=(nq+r)-(nq'+r)=nq-nq'
= n( q - q ') qui est un multiple de n puisque q-q' est un entier.
Propriété 1. 7
Soit a, b, c, d des entiers naturels et n un entier naturel non nul.
Si a = b [ n] et c = d [ n] alors :
- a+ c = b + d [ n] et a - c = b - d[n]
- pa = pb [ n] pour tout entier naturel p
- ac = bd[n]
- aP = bP [ n] pour tout entier naturel p
Des démonstrations de certaines de ces propriétés sont proposées dans l' exercice
corrigé 1.45.
Exemples
À partir des congruences 2 014 = l [3] et 1 000 = l [3], les propriétés précédentes
permettent d'obtenir facilement d'autres congruences :
2 014 + l 000 = l + l [3] c'est-à-dire 3014 = 2[3]
20 x 2 014 = 20 x l [3] c'est-à-dire 40 280 = 20[3] donc 40 280 = 2[3]
2 014 x l 000 = l x l [3] c'est-à-dire 2 014 000 = l [3]
2 014
70
= 1
70 [3] c'est-à-dire 2 014
70
= l [3] (sur cet exemple , on vient de montrer
très facil ement que le re ste de la division euclidienne de 2 014
70 par 3 est l, ce
qui n'avait rien d'évident ... ).