Vom folosi mica teoremă a lui Fermat:

* $a^M-1^ ≡ 1 (mod M), unde M este număr prim.$

* $a^N-1^ ≡ 1 (mod N), unde N este număr prim.$

Vom avea $2^K^ = (M - 1) * Q + R$, deci:

Vom avea $M = (N - 1) * K + Rest$, deci:

* $(a^2^)^K^ (mod M) ≡ (a^(M-1)^)^q^ * (a^R^) (mod M) ≡ 2^K^ * a^R^ (mod M) ≡ a^R^ (mod M)$
 
Înlocuind $a$ cu $N-1$ în relaţia de mai sus, obţinem $[(N-1)^2^]^K^ (mod M) ≡ (N-1)^R^ (mod M)$. Vom calcula mai întâi $R$, ridicând la putere $2$ la $K$ şi reţinând restul împărţirii la $M-1$. Apoi, vom ridica la $N-1$ la puterea $R$, reţinând restul împărţirii la $M$.

* $a^M^ (mod M) ≡ (a^(N-1)^)^K^ * (a^Rest^) (mod M) ≡ 2^K^ * a^Rest^ (mod M) ≡ a^Rest^ (mod M)$

==include(page="template/monthly-2014/footer")==