Dimostrazione del fatto che b^d = m (mod n)

Primo passo: Si ha:  m ^ad = m (mod p) e  m ^ad = m (mod q)

Dimostrazione: Siccome ad = 1 (mod p-1), ad è della forma: ad = k(p-1) + 1.

Quindi m ^ad =       m ^k(p-1)+1 = m ^k(p-1).m = (m ^(p-1))^k.m.

Per il piccolo teorema di Fermat, si ha m^(p-1)=1 (mod p).

Quindi  m^ad = (m ^(p-1))^k.m = 1^k.m (mod p); cioè m^ad = m (mod p).

Nello stesso modo si dimostra che  m^ad = m (mod q).

Secondo passo: usando il primo passo si conclude.

Siccome m^ad = m (mod p), m^ad è della forma: m^ad = tp + m.

Nello stesso modo: m^ad = sq + m . Quindi tp = sq.

Siccome p è primo e siccome p divide sq, p divide s o p divide q (lemma di Gauss).

Però p non può dividere q perchè q è primo. Quindi p divide s, cioè s è della forma: s = hp.

Pertanto m^ad = sq + m = hpq + m = hn + m, e m^ad = m (mod n).