n Dans tout ce qui suit,désigne un entier naturel supérieur ou égal à 2.
1. Propriétéfondamentale:
Terminale S spécialité
abna−b Deux entiers relatifset ontle même reste dans la division euclidienne parsi et seulement siest n un multiple de.
Démonstration: Implication=>● a bn Soient etdeux entiers relatifs ayant le même reste dans la division euclidienne par. a=n qr0rn où b=nq 'r a−b=n qr−nq '−ra−b=nq−q 'q−q '∈ ℤa−bn donc ,avec .Il vient queest un multiple de. ● Réciproque:<=a ba−bn Soient etdeux entiers relatifs tels queest un multiple de. a=nqr0rn b=nq 'r '0r 'n Donc avecet avec. a−b=knk ,∈ ℤ En outre,. nqr−nq '−r=nkr−r '=nk−qq ' En soustrayant membre à membre, on obtient<=> ,avec k−qq '∈ℤr−r 'n . Doncest un multiple de. 0rn0r 'n−nr−r 'n Or, et, donc. n Par ailleurs, la liste des multiples deest: M(n) = {...;-2n ;-n; 0;n;2n ; 3n ;...} r−r '=0⇔r=r ' Il vient que. D'où l'équivalence.
2. Ladéfinition:
n∈ℕ, n2a ,b∈ ℤ , . a bn ab On dit queet sontcongrus modulolorsque et ontle même reste dans la division euclidienne n par . a≡b[n] On note alors.
Exemples: ●−37≡18[11]−37=11×−470r1118=11×170r11 car ,et ,. -37et 18 ont bien le même reste dans la division par n. ●n≡3[5]n=5k3,k∈ℤ Écrire signifieque
3. Propriétés:
n∈ℕ, n2a ,a ', b etb '∈ℤ Soit ,. ➢a≡b[n]a '≡b '[n]aa '≡bb '[n] Si et, alors ➢a≡b[n]a '≡b '[n]a−a '≡b−b '[n] Si et, alors ➢a≡b[n]a '≡b '[n]aa '≡bb '[n] Si et, alors p p ➢a≡b[n]a≡b[n] Si alorspour tout entier naturel p non nul,.
Démonstration: ➢ Addition:2 a≡b[n]a '≡b '[n]a−b='nk a−b '=nk 'ck , k '∈ℤ et doncet ave. a−ba '−b '=nknk '⇔aa '−bb '=nkk 'kk '∈ℤ Avec . aa '−bb '=, Qn Q∈ℤ donc a + a' est bien congrus à b + b' modulo n.
➢ Soustraction(même raisonnement)
Multiplication:➢ a−b=nka '−b '=n k 'a=nkba '=nk 'b ' On aet doncet . aa '=bnkb 'nk 'aa '=bb 'nk ' bnkb 'n² kk ' On multiplie membre à membre:<=> <=> aa '=bb 'nbk 'kb 'nkk 'bk 'kb 'nkk '∈ ℤ avec . aa '=bb 'nK , K∈ℤaa '−bb '=nK Donc <=>d'où le résultat.
➢ Élévationàlapuissancep:Preuve par récurrence: Initialisation: 11 a=aetb=.a≡b[n] Si p = 1,bOr . Hérédité: p p a≡b[n] Supposons qu'il existe un rang p pour lequel on ait. a≡b[n] On a aussi l'hypothèseet on sait également que la relation de congruence est compatible avec la multiplication. D'où: p pp1p1 × ≡× [] ≡[ ] a ab bn<=>a bn. p p Conclusion:∀p∈ℕ, p1,a≡b[n].
Remarque:la relation de congruence n'est pas compatible avec la division.
20≡10[5] Contre-exemple: sil'on divise par 5 de chaque côté, 4 n'est pas congru à 2 modulo 5 car 4 – 2 n'est pas un multiple de 5!