220
7 La cryptographie ` a cl´ e publique
avec m < p, alors p | np = mq, et de par la proposition 7.5(4), soit p | m, soit p | q, ce
qui est absurde. Au total, le nombre d’entiers de S qui sont relativement premiers avec
pq est
pq − 1 − (p − 1) − (q − 1) = pq − p − q + 1 = (p − 1)(q − 1).
Th´ eor` eme 7.9 (th´ eor` eme d’Euler et petit th´ eor` eme de Fermat) Si m < n
est relativement premier avec n, alors m
φ(n)
≡ 1 (mod n). (Quand n est premier, le
r´ esultat, prouv´ e par Fermat et qui se lit m
n−1
≡ 1 (mod n), est appel´ e petit th´ eor` eme
de Fermat.)
Preuve Commen¸ cons par le cas o` u n est premier. Dans ce cas φ(n) = n − 1, car les
nombres 1, 2, . . . , n − 1 sont relativement premiers avec n. Soit m ∈ E = {1, . . . , n − 1}.
Prenons les produits
1 · m, 2 · m, . . . , (n − 1) · m.
(7.3)
Les restes r i , i = 1, . . . , n − 1, de la division de ces produits par n (i · m ≡ r i (mod n))
forment une permutation de 1, . . . , n − 1. En effet, le reste r k de la division de k · m par
n ne peut ˆ etre nul si n est premier et k, m < n. Donc, il appartient `
a E. De plus, les
nombres r j sont deux `
a deux distincts. En effet, supposons que k 1 · m et k 2 · m ont le
mˆ eme reste lorsqu’on les divise par n. On peut supposer k 1 ≥ k 2 . Alors,
k 1 · m = q 1 · n + r,
k 2 · m = q 2 · n + r.
D’o` u
(k 1 − k 2 ) · m = (q 1 − q 2 ) · n
Donc, n divise (k 1 − k 2 ) · m. Comme n est premier et 0 ≤ k 1 − k 2 < n et m < n, la seule
possibilit´ e est k 1 = k 2 .
En multipliant tous les restes r i et en travaillant modulo n, on obtient donc
(n − 1)! = 1 · 2 · 3 · · · (n − 1) = r 1 · r 2 · · · · · r n−1
≡ (m · 1) · (m · 2) · · · (m · (n − 1)) (mod n)
= m
n−1
· (n − 1)!.
Ceci entraˆ ıne que n | (m
n−1
− 1) · (n − 1)!. Comme n est premier, on a (n, (n − 1)!) = 1.
Donc, n | m
n−1
− 1, ce qui est ´ equivalent au r´ esultat m
n−1
≡ 1 (mod n).
La preuve est presque identique dans le cas o` u n n’est pas premier. Dans ce cas, au
lieu de prendre tous les nombres 1, 2, . . . , n− 1, on prend seulement le sous-ensemble des
nombres k qui sont relativement premiers avec n. Il y en a φ(n). Comme pr´ ec´ edemment
on les multiplie par m et on prend le reste de la division de ces produits k · m par n.
Comme pr´ ec´ edemment, ces restes sont non nuls. Si m est relativement premier avec
n, on obtient une permutation des nombres pr´ ec´ edents. En effet, si on suppose comme
7 La cryptographie ` a cl´ e publique
avec m < p, alors p | np = mq, et de par la proposition 7.5(4), soit p | m, soit p | q, ce
qui est absurde. Au total, le nombre d’entiers de S qui sont relativement premiers avec
pq est
pq − 1 − (p − 1) − (q − 1) = pq − p − q + 1 = (p − 1)(q − 1).
Th´ eor` eme 7.9 (th´ eor` eme d’Euler et petit th´ eor` eme de Fermat) Si m < n
est relativement premier avec n, alors m
φ(n)
≡ 1 (mod n). (Quand n est premier, le
r´ esultat, prouv´ e par Fermat et qui se lit m
n−1
≡ 1 (mod n), est appel´ e petit th´ eor` eme
de Fermat.)
Preuve Commen¸ cons par le cas o` u n est premier. Dans ce cas φ(n) = n − 1, car les
nombres 1, 2, . . . , n − 1 sont relativement premiers avec n. Soit m ∈ E = {1, . . . , n − 1}.
Prenons les produits
1 · m, 2 · m, . . . , (n − 1) · m.
(7.3)
Les restes r i , i = 1, . . . , n − 1, de la division de ces produits par n (i · m ≡ r i (mod n))
forment une permutation de 1, . . . , n − 1. En effet, le reste r k de la division de k · m par
n ne peut ˆ etre nul si n est premier et k, m < n. Donc, il appartient `
a E. De plus, les
nombres r j sont deux `
a deux distincts. En effet, supposons que k 1 · m et k 2 · m ont le
mˆ eme reste lorsqu’on les divise par n. On peut supposer k 1 ≥ k 2 . Alors,
k 1 · m = q 1 · n + r,
k 2 · m = q 2 · n + r.
D’o` u
(k 1 − k 2 ) · m = (q 1 − q 2 ) · n
Donc, n divise (k 1 − k 2 ) · m. Comme n est premier et 0 ≤ k 1 − k 2 < n et m < n, la seule
possibilit´ e est k 1 = k 2 .
En multipliant tous les restes r i et en travaillant modulo n, on obtient donc
(n − 1)! = 1 · 2 · 3 · · · (n − 1) = r 1 · r 2 · · · · · r n−1
≡ (m · 1) · (m · 2) · · · (m · (n − 1)) (mod n)
= m
n−1
· (n − 1)!.
Ceci entraˆ ıne que n | (m
n−1
− 1) · (n − 1)!. Comme n est premier, on a (n, (n − 1)!) = 1.
Donc, n | m
n−1
− 1, ce qui est ´ equivalent au r´ esultat m
n−1
≡ 1 (mod n).
La preuve est presque identique dans le cas o` u n n’est pas premier. Dans ce cas, au
lieu de prendre tous les nombres 1, 2, . . . , n− 1, on prend seulement le sous-ensemble des
nombres k qui sont relativement premiers avec n. Il y en a φ(n). Comme pr´ ec´ edemment
on les multiplie par m et on prend le reste de la division de ces produits k · m par n.
Comme pr´ ec´ edemment, ces restes sont non nuls. Si m est relativement premier avec
n, on obtient une permutation des nombres pr´ ec´ edents. En effet, si on suppose comme