II. Démonstrations.
II.1. Petit théorème de Fermat
Soient p un nombre premier et a dans N*. Alors p divise ap - a.
II.2. Preuve.
Cela se démontre par récurrence sur a dans N*.
Pour a = 1, on a effectivement 1p - 1 = 0 x p.
Supposons maintenant que p divise ap - a et montrons que p divise (a + 1)p - (a + 1).
(a + 1)p = ap + 
+ 1.
Or 
k dans {1, 2,..., p - 1},
p | C
car :
k!C
=
= p(p -
1)...(p + k - 1) et p | p(p - 1)...(p +
k - 1). De plus p et k sont premiers entre eux car p est
premier et k est dans {1, 2,..., p - 1}. Donc par le théorème
de Gauss, p divise C
.
Ainsi p divise 
, donc il
existe q dans N tel que 
= qp. Et par hypothèse de récurrence, il existe r
dans N tel que ap = rp + a.
Donc on a :
(a + 1)p = (r + q)p + a + 1 i.e. p divise (a + 1)p - (a + 1).
II.3. Corollaire.
Soient p un nombre premier et a dans N* tels que p ne divise pas a. Alors comme p divise a(ap - 1 - 1), par le théorème de Gauss, p divise ap - 1 - 1.
II.4. Démonstration du principe mathématique sur lequel repose le système R.S.A.
Montrons que CD = B (mod n).
Par hypothèse E est premier avec (p - 1)(q - 1). Ainsi d'après l'identité de Bézout, il existe (D, F) dans N x Z tel que DE + F(p - 1)(q> - 1) = 1 i.e. F(p - 1)(q - 1) = 1 - DE. Donc il existe D dans N tel que DE - 1 soit divisible par (p - 1)(q - 1).
Or C = BE (mod n), donc C - BE est un multiple de n. De plus comme CD - BED = (C - BE)(CD-1 + BECD-2 +...+ BED-2C + BED-1), CD - BED est aussi un multiple de n.
Si B n'est divisible ni par p ni par q, alors, par le petit théorème de Fermat, p et q divisent respectivement Bp-1 - 1 et Bq-1 - 1. Donc p et q divisent B(p-1)(q-1) - 1 car cet entier est multiple de Bp-1 - 1 et Bq-1 - 1.
Or comme DE - 1 est divisible par (p - 1)(q - 1), il existe k> dans N* tel que DE - 1 = k(p - 1)(q - 1). Ainsi on a :
BED - B = B1+k(p-1)(q-1) - B = B(Bk(p-1)(q-1) - 1) = B(B(p-1)(q-1) - 1)(B(k-1)(p-1)(q-1) +...+ 1).
Donc BED - B est divisible par n = pq. Comme CD - B = (CD - BED) + (BED - B), CD - B est divisible par n.
Donc CD = B (mod n).
