Największy wspólny dzielnik (algorytm Euklidesa)
Wyznaczanie największego wspólnego dzielnika jest jednym z tych zadań, które prawie każdy pamięta z lekcji matematyki z pierwszych klas podstawówki. Wyznaczanie największego wspólnego dzielnika (NWD) dwóch liczb ma spore znacznie w teorii liczb, bowiem pozwala skracać ułamki i w ten oto sposób ułatwiać dalsze działania.
Sam algorytm Euklidesa został stworzony około 300 roku p.n.e. i można go uważać za jeden z pierwszych algorytmów. Oczywiście NWD można wyznaczać sprawdzając wszystkie podzielniki dwóch liczb, jednak algorytm zaproponowany przez Euklidesa działa znacznie szybciej i jest po prostu lepszy.
Sprecyzujmy warunki algorytmu:
Dane: dwie naturalne liczby a i b
Wynik: liczba d, która jest największym wspólnym dzielnikiem
liczb a i b, tzn. że a dzieli się bez reszty przez d, b dzieli się bez reszty d i nie istnieje
żadna większa liczba całkowita od d, dla której a dzieli się bez reszty przez tę liczbę i b dzieli się bez
reszty przez tę liczbę
Algorytm Euklidesa (wersja 1) w postaci listy kroków
-
Dopóki liczba a jest różna od liczby b wykonujemy:
- Jeśli liczba a jest większa od b, to liczbie a przypisujemy różnicę liczb a i b
- Jeśli natomiast liczba b jest większa od a, to liczbie b przypisujemy różnicę liczb b i a
- Element d (czyli największy wspólny dzielnik) to liczba a (lub liczba b, bo obie liczby a i b są sobie równe)
Mimo że sam algorytm jest bardzo prosty, to należy Ci się wyjaśnienie, skąd wiadomo, że algorytm działa dobrze. Przede wszystkim algorytm opiera się na twierdzeniu, że NWD dwóch liczb a i b jest równy NWD wartości bezwzględnej różnicy tych liczb, czyli NWD(a, b)=NWD(a, |a - b|)
Dowód jest bardzo prosty. Ponieważ d jest największym wspólnym dzielnikiem obu liczb, to oczywiście znaczy, że jest dzielnikiem każdej liczby z osobna. Możemy zatem zapisać:
a = x · d
b = y · d
gdzie x i y są pewnymi liczbami naturalnymi. Skoro tak, to zbadajmy różnicę liczb a i b:
a - b = x · d - y · d = d · (x - y)
Gdy różnicę liczb x i y oznaczymy jako z, gdzie z jest liczbą naturalną, to otrzymamy:
a - b = d · z
co oznacza, że d jest podzielnikiem różnicy liczb a i b. Skoro tak, to znaczy, że d jest podzielnikiem liczby a, liczby b i różnicy liczb a i b (tak naprawdę wartości bezwzględnej różnicy tych liczb). Oznacza to, że możemy w takim razie szukać liczby d pośród liczby a i różnicy liczb a i b lub pośród b i różnicy liczb a i b bez utraty ogólności, czyli inaczej mówiąc udowodniliśmy, że NWD(a, b)= NWD(a, |a - b|)
Mam nadzieję, że w ten oto sposób przekonałem Cię o poprawności twierdzenia. W tej wersji algorytm jest wykonywany tak długo jak liczby a i b są różne, bowiem gdy liczby są sobie równe, to znaczy, że ich wartość jest oczywiście ich największym wspólnym dzielnikiem.
