CONGRUENCES BTS TS SPE MATHS 2011
1. CONGRUENCE .
Soit a et a ' deux entiers relatifs.
Soit m un entier naturel non nul.
a et a' sont congrus modulo m quand on a l'une
des affirmations équivalentes suivantes qui est vraie.
• a et a' ont le même reste dans la division par m . ( 1 )
• a − a' est un multiple de m . ( 2 )
• Il existe un entier relatif k tel que a − a' = k× m ( c-à-d a − a ' est un multiple de m )
• Il existe un entier relatif k tel que a = a ' + k× m ( c-à-d a et a ' sont égaux à un multiple de m près )
JUSTIFICATION:
Montrons que : ( 1 ) <=> ( 2 )
• ( 1 ) => ( 2 )
On sait que : a et a' ont le même reste dans la division par m .
Donc : Il existe deux entiers relatifs uniques q et r tels que
a = m × q + r avec 0 ≤ r < m
De plus:
Il existe deux entiers relatifs uniques q' et r' tels que
a' = m × q' + r' avec 0 ≤ r' < m
Enfin r = r ' c-à-d r − r ' = 0 comme a et a' ont le même reste dans la division par m .
D'où : a - a ' = m × q + r − ( m × q' + r' ) = m × ( q − q ' ) + r − r '
c-à-d a − a ' = m × ( q − q ' )
q − q' est un entier relatif que l'on peut noter k.
On a: a − a ' = m × k
Ainsi: a − a ' est bien un multiple de m
On a bien montré l'implication.
• ( 2 ) => ( 1 )
On sait que : a − a ' est bien un multiple de m .
Donc il existe un entier relatif k tel que a − a' = k × m
c-à-d tel que a = a' + k × m
On a en divisant a par m et a ' par m :
Il existe deux entiers relatifs uniques q' et r' tels que
a' = m × q' + r ' avec 0 ≤ r' < m
Il existe deux entiers relatifs uniques q et r tels que
a = m × q + r avec 0 ≤ r < m
Donc a = a' + k × m se traduit par :
a = m × q ' + r ' + m k
c-à-d a = m ( q' + k ) + r' avec 0 ≤ r' < m
D'après l'unicité du quotient et du reste pour la division de a par m
il vient : q' + k = q et surtout r = r'
a et a ' ont bien le même reste .
On a l'implication réciproque.
Conclusion : L'équivalence est avérée.
2. NOTATION.
a et a' sont congrus modulo m s'écrit :
a ≡ a ' ( m ) ou a ≡ a ' [ m ] a ≡ a ' Modulo m
3. PROPRIETE DES CONGRUENCES.
Soit a et a ' deux entiers relatifs.
Soit b et b ' deux entiers relatifs.
Soit m dans IN*.
Soit p dans IN*. Soit k un entier relatif.
Soit a ≡ a ' ( m ) et b ≡ b ' ( m )
Alors :
a − b ≡ a ' − b' ( m )
a + b ≡ a ' + b' ( m )
a × b ≡ a ' × b' ( m )
ap ≡ a' p ( m )
k a ≡ k a' ( m )
4. EXEMPLE:
Montrer que pour tout entier naturel n on a:
53n − 6n ≡ 0 [ 1 7 ]
Réponse: Au lieu de penser faire une récurrence sur IN on peut dire:
On a : 53n = ( 53 ) n pour tout n dans IN
Or 53 = 125 = 17 × 7 + 6 0 ≤ 6 < 17
Donc 53 ≡ 6 [ 17 ]
D'où ( 53 )n ≡ 6n [ 17 ] pour tout entier naturel n
c-à-d 53n ≡ 6n [ 17 ] pour tout entier naturel n
c-à-d 53n − 6n ≡ 0 [ 1 7 ] pour tout entier naturel n
C'est ce que l'on voulait.
Le résultat est prouvé sur IN.
--------------------------------------------------------------------------------------