A 2-a solutie, se bazeaza pe un simplu principiu. Anume cel al euclidului extins, si anume ca exista doua numere $A$ si $B$, intregi, astfel incat $A$ * $N$ + $B$ * $P$ = cmmdc($N$,$P$). Nu voi intra in detalii in legatura cu algoritmul de gasire a acestor numere $A$ si $B$, algoritm care se gaseste in Cormen sau chiar pe infoarena( http://infoarena.ro/problema/euclid3). Se presupune ca le putem gasi in complexitate O( $M$ ). cmmdc( $N$ , $P$ ) = 1, deoarece $N$ ≤ $P -  1$ iar $P$ este prim. Deci avem ca $A$ * $N$ + $B$ * $P$ = $1$, ecuatie care o transformam in Z{~p~} ,in alte cuvinte modulo $P$, si rezulta $A$ * $N$ + $0$ = $1$, fiindca $B$ * $P$ e divizibil cu $P$,din motive evidente. $A$ * $N$ = $1$ (% $P$ ), Se observa din nou ca $A$ este $X$ -ul cautat. Din pacate acum $A$ -ul poate sa fie si negativ, deci trebuie sa adaugam $P$ la $A$ pana devine pozitiv. Complexitatea O(log{~2~} $P$ ).
h4. Avantaje/ Dezavantaje

Ne vom referi la primul algoritm optim(cel cu ridicarea la putere) ca prima rezolvare si la celalalt algoritm ca a 2a rezolvare ,pentru dezambiguizare.
Prima rezolvare are urmatoarele avantaje: e usor de demonstrat si implicit de tinut minte, e usor de implementat si nu foloseste functii recursive si nici nu face operatii care sa incetineasca programul. Dezavantajul consta in faptul ca solutia nu e flexibila si nu poate fi extinsa pentru cazul cand cmmdc({$P$},{$N$}) = $1$.
A 2-a rezolvare e mai greu de implementat, poate da overflow si in practica se comporta mai prost decat prima, desi complexitatea e aceeasi. Dar aceasta problema poate fi adaptata pentru cazul cand $P$ nu este prim si se stie doar ca $N$ si $P$ sunt relativ prime, in alte cuvinte au cmmdc({$P$},{$N$}) = $1$.
h4. Probleme externe

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2115