Rozszerzony algorytm Euklidesa

Podstawowa wersja algorytmu Euklidesa pozwala wyznaczyć największy wspólny dzielnik dla dwóch liczb naturalnych. Rozszerzona wersja tego algorytmu dodatkowo rozwiązuje równanie diofantyczne:

$$NWD(a,\ b)=a\cdot x+b\cdot y$$

wyznaczając wartości całkowite liczb x oraz y, na przykład dla liczb 13 i 5 mamy:

$$NWD(13,5)=1=13\cdot 2 + 5\cdot (-5)$$

a więc $$x=2,\ y=-5$$

Opis algorytmu

Po pierwsze należy zauważyć, że dla dowolnych trzech liczb całkowitych  $$a,\ b,\ c$$ zachodzi:

jeśli $$\frac{a}{b}=c,\ b\neq 0$$ to $$a=b\cdot c + r$$, gdzie r, to reszta z dzielenia liczb a przez b

Do opisania algorytmu posłużymy się powyższym przykładem:

Krok 1.

wynik dzielenia całkowitego liczby a przez b: $$13\ div\ 5 = 2$$ 

reszta z dzielenia całkowitego liczby a przez b: $$13\ mod\ 5 = 3$$

a więc liczbę 13 można zapisać

(1) $$13 = 2\cdot 5 +3$$

W każdym kolejnym kroku będziemy brać liczbę przez którą dzieliliśmy i otrzymaną resztę, a więc w kroku następnym liczbę 5 i 3.

Krok 2.

$$5\ div\ 3 = 1$$ 

$$5\ mod\ 3 = 2$$

liczbę 5 możemy przedstawić w postaci równania:

(2) $$5 = 1\cdot 3 +2$$

tym razem dzieliliśmy przez 3, a uzyskana reszta to 2.

Krok 3.

$$3\ div\ 2 = 1$$ 

$$3\ mod\ 2 = 1$$

(3) $$3 = 1\cdot 2 +1$$

dzieliliśmy przez 2, a uzyskana reszta to 1.

Krok 4.

$$2\ div\ 1 = 2$$ 

$$2\ mod\ 1 = 0$$

$$2 = 2\cdot1+0$$

Pamiętamy z algorytmu Euklidesa (wersja optymalna), że gdy otrzymujemy resztę równą 0, to NWD liczb jest poprzednia reszta, w tym przykładzie jest to 1.

Z każdego równania z otrzymanych kroków (nie licząc kroku 4), wyznaczamy resztę:

(1) $$3 = 1\cdot 13 - 2\cdot 5$$

(2) $$2 = 1\cdot 5 -1\cdot 3$$

(3) $$1 = 1\cdot 3 -1\cdot 2$$

Teraz do równania (3) podstawiamy za $$3$$ resztę z równania  (2), a do drugiego resztę z równania (1):

 $$1=1\cdot 3-1\cdot 2=1\cdot 3-1\cdot (1\cdot 5 -1\cdot 3)=$$

$$- 1\cdot 5+2\cdot 3=-1\cdot 5+2\cdot(1\cdot 13-2\cdot 5)=$$

$$2\cdot 13-5\cdot 5$$

W ten sposób znaleźliśmy szukane wartości x i y. Problem ten można w prosty sposób rozwiązać rekurencyjnie.

Implementacja rekurencyjna algorytmu 

#include<iostream>
using namespace std;

int x, y;
void euklides(int a, int b)
{
	if(b!=0)
	{
		euklides(b, a%b);
		int pom = y;
		y = x  - a/b*y;
		x = pom;
	}
}
int main()
{
	x = 1, y = 0;
	int a, b;
	
	cout<<"Podaj liczby: ";
	cin>>a>>b;
	
	euklides(a, b);
	
	cout<<"nwd("<<a<<", "<<b<<") = "
	<<a<<" * "<<x<<" + "<<b<<" * "<<y<<" = "
	<<a*x+b*y<<endl;
	
	return 0;
}