Algorytm Euklidesa

Algorytm Euklidesa – algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. Nie wymaga rozkładania liczb na czynniki pierwsze. Algorytm wymyślił Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie zawarł go w swoim dziele Elementy W algorytmie wykorzystywana jest zależnośćPrzebieg algorytmu Euklidesa obliczania NWD liczb a i b:Zapis w pseudokodzie:StądJeżeli największym wspólnym dzielnikiem dwóch liczb jest 1 to są one względnie pierwsze. Przykład dla 46406 i 36957:Lemat: Z lematu wynika przez indukcję, że jeśli algorytm się zakończy, to da poprawny wynik. Pozostaje udowodnić, że się zakończy. Wystarczy w tym celu zauważyć, że , więc w każdym kroku algorytmu wartość zmniejsza się przynajmniej o 1 Ponieważ nie może nigdy być ujemna, algorytm musi się zakończyć.Dla dowolnych liczb algorytm Euklidesa zwraca wartość NWD(m, n) po co najwyżej przebiegach pętli.Największej liczby kroków algorytmu wymagają dwa kolejne elementy ciągu Fibonacciego.Jeśli przechowywana będzie informacja o kolejnych ilorazach, to będzie też można wyznaczyć liczby całkowite w równaniu . Ta metoda nazywana jest rozszerzonym algorytmem Euklidesa Na przykład dla liczb 174 i 18 w algorytmie Euklidesa uzyskuje się wyniki pośrednie:lub przepisując wszystkie równania w taki sposób, by w pierwszym równaniu po prawej stronie występowała tylko suma pewnych wielokrotności liczb 174 i 18:Zauważmy, że w pierwszym równaniu po prawej stronie występuje kombinacja liniowa liczb 174 i 18 podobnie jak w równaniu . W następnych równaniach po prawej stronie mamy zawsze kombinację liniową liczb 174 18 lub liczb, które wystąpiły po lewej stronie we wcześniejszych równaniach.Kluczowa dla rozszerzonego algorytmu Euklidesa staje się możliwość stopniowego zastępowania tych liczb przez kombinacje liniowe liczb wejściowych aż do otrzymania równości:np.Zapis algorytmu w pseudokodzie: