Pentru prima solutie trebuie sa apelam la teorema lui Ferma care zice ca pentru orice $P$ prim si $N$ , $1 ≤ N ≤ P$, se verifica relatia:
$N$^{$P$}^ = {$N$} (%{$P$}).
Pentru intelegerea mai buna a solutiei doresc sa mentionez ca Z{~p~} cu inmultirea formeaza un grup, si asta inseamna ca orice element din Z{~p~} are un invers, unic, deci putem inmulti prin el, chiar daca nu il stim.

In alte cuvinte $N$^{$P$}^ = {$N$} (%$P$) | * $N$^-1^

In alte cuvinte $N$^{$P$}^ = {$N$} (%{$P$}) | * $N$^-1^

$N$^{$P-1$}^ = {$1$} (%{$P$}), deci :
$N$ * $N$^{$P-2$}^ = {$1$} (%{$P$});
De unde se observa ca $N$^{$P-2$}^ este defapt $X$ -ul cautat. Deci solutia, pe scurt pentru cei care nu sunt prea interesati de demonstratie este sa ridicam $N$ la puterea $P-2$ modulo $P$, si acest numar va fi rezultatul dorit. Ridicarea la putere se face in timp logaritmic, deci complexitate finala este O(log ~2~ $P$). O astfel de implementare se poate vedea aici http://infoarena.ro/job_detail/223243?action=view-source .