Jak obliczyć największy wspólny dzielnik dwóch liczb całkowitych?

Sporo osób pamięta różne "metody" obliczania największego wspólnego dzielnika i chętnie raczy nimi pytających, więc na początek podamy przykład, pozwalający łatwo ocenić praktyczną przydatność różnych metod:

Obliczyć NWD(2²²⁰ +1, 2²²³ + 1).

Nieznany jest ani jeden właściwy dzielnik żadnej z tych dwóch liczb (Fermata). Praktycznym i szybkim sposobem obliczania największego wspólnego dzielnika dwóch liczb całkowitych jest algorytm Euklidesa. Algorytm wykorzystuje nastepujące proste spostrzeżenie:

NWD(a, b) = NWD(b, a - kb).

Rzeczywiście, jeśli d jest wspólnym dzielnikiem liczb a i b, powiedzmy a = da' i b = db' to a - kb = da' - kdb' = d (a' - kb'), czyli d jest wspólnym dzielnikiem liczb a i a - kb. Odwrotnie, jesli d jest wspólnym dzielnikiem liczb b i c = a - kb, to - na podstawie już udowodnionego - d jest wspólnym dzielnikiem liczb b i c - (- k)b = a. To oznacza, że pary liczb a, b oraz b, a - kb mają te same zbiory wspólnych dzielników, a zatem i ten sam największy wspólny dzielnik. A teraz sam algorytm; ponieważ

NWD(a, b) = NWD(| a|,| b|),

oraz

NWD(a, 0) = a

więc wystarczy umieć obliczyć największy wspólny dzielnik dwóch liczb naturalnych. Pierwszy krok: dzielimy a przez b z resztą:

a = i₁ ^. b + r₁ i 0 $$\leq$$ r₁ < b;

otrzymujemy

r₁ = a - i₁ ^. b i NWD(a, b) = NWD(b, a - i₁ ^. b) = NWD(b, r1).

Drugi krok: dzielimy b przez r₁ z resztą:

b = i₂ ^. r₁ + r₂ i 0 $$\leq$$ r₂ < r₁;

otrzymujemy

r2 = b - i₂r₁ i NWD(b, r₁) = NWD(r₁, b - i₂ ^. r₁) = NWD(r₁, r₂).

Trzeci krok: dzielimy r₁ przez r₂ z resztą, itd. - w każdym kroku dzielimy z resztą przedostatnią resztę przez ostatnią.

Rezultatem jest malejący ciąg liczb b > r₁ > r₂ >... i równości:

NWD(a, b) = NWD(r_n, r_n+1).

Ale nie może istnieć nieskończony malejący ciąg liczb naturalnych! Ciąg reszt musi się urwać, czyli po pewnym r_m nie ma już następnej reszty. Ale to, że nie można podzielić z resztą liczby r_m-1 przez r_m oznacza, że r_m = 0. Wobec tego

NWD(a, b) = NWD(r_m-1, r_m) = NWD(r_m-1, 0) = r_m-1.

Największym wspólnym dzielnikiem liczb a, b jest ostatnia niezerowa reszta r_m-1 w algorytmie Euklidesa. W naszym testowym przykładzie:

2²²³ + 1 = 2²²³ -1 + 2 = 2²²²⁺¹ - 1 + 2 =

= 2^{2 . 222} -1 + 2 = (2²²²)² -1² + 2 =

= (2²²² +1)(2²²² - 1) + 2 =

= (2²²² +1)(2²²¹ +1)(2²²¹ - 1) + 2 =

= (2²²² +1)(2²²¹ +1)(2²²⁰ -1)(2²²⁰ + 1) + 2

czyli pierwszą resztą jest 2. Dalej:

2²²⁰ +1 = 2^{220-1 .} 2 + 1

więc drugą resztą jest 1, a trzecią resztą jest 0. Wobec tego

NWD(2²²⁰ +1, 2²²³ + 1) = 1.

Najwolniej algorytm Euklidesa działa dla pary kolejnych liczb Fibonacciego. Zatem liczba m dzieleń w algorytmie Euklidesa nie przekracza log_$\phi$(b$\sqrt{{5}}$) < 4 + log_$\phi$(b), gdzie $\phi$ = (1 + $\sqrt{{5}}$)/2,

m < 4 + log_$\phi$(b) = 4 + $${\frac{{\log (b)}}{{\log (\phi)}}}$$ < 4 + 5 log(b).