7.2 Quelques outils de th´ eorie des nombres
215
• (a, b) | a et (a, b) | b ;
• Si d | a et d | b, alors d | (a, b).
(iii) On dit que a est congru ` a b modulo n si n | (a − b), c’est-` a-dire s’il existe x ∈ Z
tel que (a − b) = nx. On note a ≡ b (mod n). La relation « ≡ (mod n) » est une
relation d’´ equivalence appel´ ee congruence modulo n.
Proposition 7.2 Soient a, b, c, d, x, y ∈ Z. Alors,
a ≡ c (mod n) et b ≡ d (mod n) =⇒ a + b ≡ c + d (mod n),
a ≡ c (mod n) et b ≡ d (mod n) =⇒ ab ≡ cd (mod n),
a ≡ c (mod n) et b ≡ d (mod n) =⇒ ax + by ≡ cx + dy (mod n).
Preuve D´ emontrons la seconde implication. Les autres sont laiss´ ees en exercice.
Puisque a ≡ c (mod n), alors n | a − c. Donc, il existe un entier x tel que a − c = nx.
De mˆ eme, il existe y tel que b − d = ny. Pour montrer que ab ≡ cd (mod n), on doit
montrer que n | ab − cd. Or,
ab − cd = (ab − ad) + (ad − cd)
= a(b − d) + d(a − c)
= nay + nxd
= n(ay + xd).
D’o` u n | (ab − cd), ce qui est ´ equivalent `
a la conclusion.
L’algorithme d’Euclide permet de trouver le PGCD, (a, b), de deux entiers a et b.
Son fonctionnement est explicit´ e dans la proposition suivante. Il fait appel `
a la notion
de division avec reste de deux entiers.
Proposition 7.3 (Algorithme d’Euclide) Soient a et b deux entiers positifs tels que
a ≥ b et soit la suite d’entiers {r i } construite de la fa¸ con suivante. On fait la division
avec reste de a par b : on nomme q 1 le quotient et r 1 le reste. On a
a = bq 1 + r 1 ,
0 ≤ r 1 < b.
De la mˆ eme mani` ere, on fait maintenant la division avec reste de b par r 1 :
b = r 1 q 2 + r 2 ,
0 ≤ r 2 < r 1 .
On it` ere. . .
r i−1 = r i q i+1 + r i+1 ,
0 ≤ r i+1 < r i .
La suite {r i } est strictement d´ ecroissante. Donc, il existe un entier n tel que r n+1 = 0.
Alors r n = (a, b).