algorytm Euklidesa

[withdrawn]

Pokazać ( używając algorytmu Euklidesa) , że \(\displaystyle{ (a,b) = nwd(a,b) := d}\) można zapisać w postaci \(\displaystyle{ ka + lb}\) gdzie \(\displaystyle{ k,l \in Z}\) tak więc w szczegolnosci jesli \(\displaystyle{ a,b}\) są wzglednie pierwsze to istnieją \(\displaystyle{ k,l \in Z}\) że : \(\displaystyle{ 1 = ka + lb}\).

[Spektralny]

Jest to tzw. rozszerzony algorytm Euklidesa:



Polego on de facto na sprytnym zapisaniu tego co dostajesz przy zwykłym algorytmie Euklidesa (działa oczywiście w ogólnych pierścieniach Euklidesowych).