Rozszerzony algorytm Eulidesa

Najwiekszy wspolny dzielnik dwoch liczb moze byæ przedstawiony w postaci 
kombinacji liniowej tych liczb ze wspolczynnikami calkowitymi:
       NWD(a, b) = x*a + y*b
Do znalezienia takiej kombinacji liniowej sluzyc moze przedstawiony 
tutaj rozszerzony algorytm Euklidesa.

Ponadto algorytm ten moze byc uzyty do znalezienia liczby odwrotnej do b mod a
Liczba odwrotna do liczby b mod a jest to liczba y spelniajaca rownanie:
b * y mod a = 1
co zapisuje sie rowniez jako
b * y ? 1 (mod a)
      Liczba ta ISTNIEJE (!),  jezeli NWD(a, b)=1.

Algorytm przebiega nastepujaco (zakladamy, ze a>b):

Przypisz poczatkowe wartosci:
  q = floor(a/b) - czesc calkowita z dzielenia a/b
  r = a - q*b - reszta z dzielenia a/b
  nwd = b - poczatkowa wartosc wyniku, gdyby juz teraz reszta wynosila 0

Zainicjuj pomocnicze zmienne do obliczenia wartosci dla kombinacji liniowej 
i odwrotnosci b mod a (UWAGA - TO CO PO LEWEJ STRONIE ZNAKU ROWNOSCI,
to sa nazwy zmiennych pomocniczych):

    xi-2 = 1
    xi-1 = 0
    xi   = 1
    yi-2 = 0  
    yi-1 = 1
    yi   = -(q-1) - poczatkowa wartosc wyniku, gdyby juz teraz reszta wynosila 0.
(czyli szesc dodatkowych zmiennych pomocniczych,xi-2,xi-1,xi,yi-2,yi-1,yi)

Dopoki reszta r jest rozna od zera wykonuj nastepujace kroki 
(i - oznacza numer iteracji, zainicjowane poczatkowo wartosci xi oraz yi 
zostaja nadpisane podczas pierwszej iteracji):
  a = b
  b = r
  xi = xi-2 -  q * xi-1
  yi = yi-2 -  q * yi-1
  i = i + 1
  nwd = r
  q = floor(a/b); - czesc calkowita z dzielenia a/b
  r = a - q*b - reszta z dzielenia a/b


Jezeli reszta wynosi 0 , to wowczas wynik przechowywany jest w zmiennej nwd.
Wspolczynniki kombinacji liniowej przechowywane sa w zmiennych xi oraz yi, 
oryginalne wartosci a oraz b zostaly zniszczone podczas prowadzenia obliczen 
wiec nalezy je zapamietac przed przeprowadzeniem obliczen.
Ponadto jezeli NWD(a, b) = 1, to liczba odwrotna do liczby b mod a jest 
przechowywana w zmiennej yi.

Przyklady

a = 6
b = 3
i	a	b	q	r	nwd	xi	xi-1	xi-2	yi	yi-1 	yi-2
1	6	3	2	0	3	1	0	1	-1	1	0

NWD(6, 3) = 3 = 1 * 6 + -1 * 3



a = 84
b = 15
i	a	b	q	r	nwd	xi	xi-1	xi-2	yi	yi-1 	yi-2
1	84	15	5	9	15	1	0	1	-4	1	0
1	15	9	1	6	9	1	0	1	-5	1	0
2	9	6	1	3	6	-1	1	0	6	-5	1
3	6	3	2	0	3	2	-1	1	-11	6	-5

NWD(84, 15) = 3 = 2 * 84 + -11 * 15



a = 26
b = 15
i	a	b	q	r	nwd	xi	xi-1	xi-2	yi	yi-1 	yi-2
1	26	15	1	11	15	1	0	1	0	1	0
1	15	11	1	4	11	1	0	1	-1	1	0
2	11	4	2	3	4	-1	1	0	2	-1	1
3	4	3	1	1	3	3	-1	1	-5	2	-1
4	3	1	3	0	1	-4	3	-1	7	-5	2

NWD(26, 15) = 1 = -4 * 26 + 7 * 15
   15 * 7 mod 26 = 1      odwrotnosci modulo 26
  (-4 * 26 mod 15 = 1)    odwrotnosci modulo 15