element odwrotny...

cześć jak to na dziewczynę przypadło potrzebuję pomocy w sprawie programu:
a^b mod n w pierścieniu Zn.

potrzebuję program który opisuje elementy odwrotne
przykładem może być 4^-1 mod 10.
Istotą całości jest to że np. -4 mod 5 to 1.
a oto przykład:
obliczyć x:
13x=1 mod 30
wyznaczamy następujące działanie 13x+30k=1
30=213+4
4=30-213
13=34+1
1=13-34=13-3(30-213)=713-330 jeśli weźmiemy teraz równość 137+30*(-3) mod 30 to otrzymamy wynik x=7 a więc 13^-1=7
potrzebuję programu który takie coś by opisywał byłabym wdzięczna za możliwie jak najszybsze rozwiązanie tego problemu :)

1/a * lx == 1 (mod b)

dla małych b

for (i=1; i<b; i++)
    if ((a*i)%b==1)
         lx=i;

Rozszerzony algorytm Euklidesa

x=0; lx=1;
y=1; ly=0;
while (b != 0) {
    t=b;
    q=a/b;
    b=a - b*q;
    a=t;

    t=x;
    x=lx - q*x;
    lx= t;

    t=y;
    y=ly - q*y;
    ly= t;
}
//if (lx<0) lx=x-lx;

mgr.Dobrowolski napisał(a)

1/a * lx == 1 (mod b)

dla małych b

for (i=1; i<b; i++)
    if ((a*i)%b==1)
         lx=i;

Rozszerzony algorytm Euklidesa

x=0; lx=1;
y=1; ly=0;
while (b != 0) {
    t=b;
    q=a/b;
    b=a - b*q;
    a=t;

    t=x;
    x=lx - q*x;
    lx= t;

    t=y;
    y=ly - q*y;
    ly= t;
}
//if (lx<0) lx=x-lx;

słucham?? niestety nic z tego nie rozumiem mógłby mi ktoś to wytłumaczyć na jakiej zasadzie co działa?? i co to jest "lx"?? i czemu "mod b"?? przecież ja mam zdefiniowaną funkcję jako a^b mod n

Nazwało mi się to i owo inaczej, moje zabawki szukają "lx" takiego, że "a*lx == 1 (mod b)", czyli "lx" jest elementem odwrotnym "a" w pierścieniu Zb.