Czym jest algorytm Euklidesa?
Algorytm Euklidesa – algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy”, w księgach siódmej oraz dziesiątej.
Pierwsze wzmianki na temat tego algorytmu pojawiły się w dziele Euklidesa zatytułowanym „Elementy”, około trzysetnego roku przed naszą erą, co sprawia, że jest jednym z najstarszych, wciąż używanych algorytmów numerycznych. Pierwsza wersja algorytmu została opisana tylko dla liczb naturalnych. W XIX wieku powstały odmiany algorytmu dla liczb całkowitych Gaussa oraz wielomianów z jedną niewiadomą. Doprowadziło to do powstania współczesnych pojęć algebry abstrakcyjnej, takich jak dziedzina Euklidesa. W późniejszych czasach opracowano odmiany algorytmu dla innych struktur matematycznych, jak węzły czy wielomiany z wieloma niewiadomymi.
Największym wspólnym dzielnikiem dwóch liczb jest największa z liczb, która dzieli obie te liczby bez reszty. Algorytm Euklidesa opiera się na założeniu, że największy wspólny dzielnik dwóch liczb nie zmienia się, jeżeli od większej liczby odejmujemy mniejszą. Dla liczb całkowitych k, m oraz n załóżmy, że k jest wspólnym czynnikiem liczb A oraz B; załóżmy też, że oraz Możemy teraz dokonać działania wiemy więc, że k jest także wspólnym czynnikiem różnicy tych liczb.
Przykład – wersja z odejmowaniem
Załóżmy, że chcemy znaleźć największy wspólny dzielnik liczb 1989 oraz 867. Jeżeli od większej liczby odejmiemy liczbę mniejszą, wartość największego wspólnego dzielnika nie ulegnie zmianie. Ponieważ 1989 – 867 = 1122, nowa para liczb wygląda następująco:
1122, 867
Ponownie odejmujemy mniejszą liczbę od większej 1122 – 867 = 255, tworząc w ten sposób kolejną parę:
867 nie jest już mniejszą liczbą. Stosując ten sam sposób, ponownie zmniejszamy wartość większej liczby o wartość mniejszej: 867 – 255 = 612, nowa para liczb to:
255, 612
Pierwsza liczba, 255, jest wciąż mniejsza, ponownie więc odejmujemy 255 od liczby większej: 612 – 255 = 357, więc kolejna para liczb to:
255, 357
357 – 255 = 102, kolejna para to:
255, 102
Teraz widać, że 255 jest większą liczbą, odejmujemy więc od niej 102, co daje nam parę:
153, 102
Odjęcie 102 od 153 tworzy nam kolejną parę:
51, 102.
Teraz odejmujemy 51 od 102, co daje nam:
51, 51
Ponieważ obie liczby są sobie równe, kolejne odejmowanie da nam zero. Oznacza to, że największym wspólnym dzielnikiem liczb 1989 i 867 jest liczba 51.