Ici sont regroupées les démonstrations dont les résultats sont nécessaires pour la compréhension du sujet. Vous pouvez télécharger toutes ces démonstrations au format pdf en cliquant ici.
Remarque : Pour les élèves de prépa, ces démonstrations sont dans votre cours de maths (de sup ou de spé suivant les filières...), il en existe d'ailleurs des différentes...

Existence de alpha :

k est premier avec phi(n) donc d'après Bezout on a :
Il existe alpha et i (ou i est entier) tels que, k*alpha + i*phi(n) = 1.
Et donc k*alpha = 1 mod [phi(n)].

Preuve de c^a = m mod [n] :

c = m^k mod [n] => n divise c-m^k.
Or c^alpha - m^(k*alpha) = (c - m^k) * (c^(alpha-1) + c^(alpha-2)*m^k + c^(alpha-3)*m^(2*k) + … + m^(k*(alpha-1))).
On en déduit que n divise c^alpha-m^(k*alpha).

Petit Théorème de Fermat :
p premier => m^p = m mod [p].
=> p divise m^p - m.

k*alpha = 1 mod [(p-1)*(q-1)] donc il existe un entier alpha tel que :
k*alpha - 1 = alpha*(p-1)*(q-1).

m^(k*alpha) - m = m*(m^(k*alpha-1) - 1)
= m*(m^(alpha*(p-1)*(q-1)) - 1)
= m*(m^(p-1) - 1)*(m^((alpha*(q-1)-1)*(p-1)) + m^((alpha*(q-1)-2)*(p-1)) + … + 1)
= (m^p - m)*(m^((alpha*(q-1)-1)*(p-1)) + m^((alpha*(q-1)-2)*(p-1)) + … + 1).

Donc, d'après le petit théorème de Fermat :
p divise m^(k*alpha) - m.

De même q divise m^(k*alpha) - m et donc n aussi.

On conclue que, comme c^alpha - m = (c^alpha - m^(k*alpha)) + (m^(k*alpha) - m) alors :
n divise c^alpha -m et donc :
c^alpha = m mod [n].

Ce qu'il fallait démontrer.

phi(p*q)= phi(p)* phi(q) avec p et q premiers :

La fonction d'Euler phi(n) est le nombre d'entiers premiers avec n et plus petits que n.
Dénombrons le complémentaire :
p , 2*p , 3*p , 4*p , … , (q-1)*p , q*p ne sont pas premiers avec p*q.
De même q , 2*q , 3*q , … , (p-1)*q ce qui fait au total p+q-1 nombres.
Donc phi(p*q) = p*q - (p+q-1) = (p-1)*(q-1) = phi(p)* phi(q)
car phi(p)=p-1 puisque p est premier.