(1) Si p es primo y a es cualquier número natural que no es múltiplo de p, entonces a^p-1 da resto 1 al dividirlo por p.

Ejemplo: p=7, a=15,
a^p-1=15^{6 =}11390625=1627232·7 + 1
 

(2) La generalización sencilla, raíz del sistema RSA:
Si p y q son primos y a es cualquier número que no es múltiplo de pq, entonces a^(p-1)(q-1)   dividido por pq  da resto 1.

Ejemplo: p=7, q=11, a=23, (p-1)(q-1)=60
23⁶⁰=
50544064300378852729810461353568392757/
15416508617402090310185410509132307928/
805601=
77·656416419485439645841694303293096009/
833170975145117154585738365001186014016/
72800 + 1