Algorytm Euklidesa - NWD i NWW krok po kroku, dowód

Q: Jak obliczyć NWW dwóch liczb?

Podziel iloczyn liczb przez ich NWD: operatornameNWW(a, b) = fracaboperatornameNWD(a, b).

Q: Co to jest tożsamość Bézouta?

Zapis NWD jako kombinacji liczb: ax + by = operatornameNWD(a, b) dla pewnych całkowitych x, y. Współczynniki wyznacza rozszerzony algorytm Euklidesa.

Q: Kiedy liczby są względnie pierwsze?

Gdy ich NWD wynosi 1 - algorytm Euklidesa kończy się wtedy resztą 1.

Algorytm Euklidesa

Dla liczb naturalnych $a \ge b > 0$ , jeśli $a = q \cdot b + r$ , gdzie $0 \le r < b$ , to

$\operatorname{NWD}(a, b) = \operatorname{NWD}(b, r), \qquad \operatorname{NWD}(a, 0) = a.$

Dzielimy z resztą, aż reszta wyniesie $0$ - ostatnia niezerowa reszta to NWD. Ponadto $\operatorname{NWW}(a, b) = \dfrac{a \cdot b}{\operatorname{NWD}(a, b)}$ .

Co mówi twierdzenie

Algorytm Euklidesa to sposób obliczania największego wspólnego dzielnika (NWD) dwóch liczb bez rozkładania ich na czynniki pierwsze. Opiera się na jednym fakcie: NWD dwóch liczb nie zmienia się, gdy większą z nich zastąpimy resztą z jej dzielenia przez mniejszą. Powtarzając ten krok, dostajemy coraz mniejsze liczby, aż reszta wyniesie zero - wtedy ostatnia niezerowa reszta jest szukanym NWD.

Algorytm działa szybko nawet dla liczb, których rozkładu na czynniki nie da się w praktyce znaleźć - dlatego jest podstawą współczesnej kryptografii.

Przykład

Obliczmy $\operatorname{NWD}(252, 198)$ :

$252 = 1 \cdot 198 + 54, \qquad 198 = 3 \cdot 54 + 36, \qquad 54 = 1 \cdot 36 + 18, \qquad 36 = 2 \cdot 18 + 0.$

Ostatnia niezerowa reszta to $18$ , więc $\operatorname{NWD}(252, 198) = 18$ . Stąd od razu:

$\operatorname{NWW}(252, 198) = \frac{252 \cdot 198}{18} = 2772$ ,
ułamek $\frac{198}{252}$ po skróceniu przez $18$ to $\frac{11}{14}$ .

Wersja z odejmowaniem. Zamiast dzielić, można odejmować mniejszą liczbę od większej: $(252, 198) \to (54, 198) \to (54, 144) \to (54, 90) \to (54, 36) \to (18, 36) \to (18, 18)$ - wynik ten sam, tylko kroków jest więcej. W takiej postaci algorytm opisał Euklides.

Założenia

$a$ i $b$ są liczbami całkowitymi, niezerowymi jednocześnie (dla liczb ujemnych bierze się ich wartości bezwzględne).
Dzielenie z resztą: dla $b > 0$ istnieją jednoznacznie wyznaczone $q$ i $r$ , że $a = qb + r$ i $0 \le r < b$ (zob. dzielenie z resztą).

Dowód poprawności

Pokaż dowódUkryj dowód

Krok 1. Te same wspólne dzielniki. Niech $a = qb + r$ . Jeśli $d$ dzieli $a$ i $b$ , to dzieli też $r = a - qb$ . I odwrotnie: jeśli $d$ dzieli $b$ i $r$ , to dzieli też $a = qb + r$ . Pary $(a, b)$ i $(b, r)$ mają więc dokładnie te same wspólne dzielniki, a zatem ten sam największy: $\operatorname{NWD}(a, b) = \operatorname{NWD}(b, r)$ .

Krok 2. Algorytm się kończy. Reszty tworzą ciąg ściśle malejących liczb nieujemnych ( $b > r_1 > r_2 > \ldots \ge 0$ ), więc po skończenie wielu krokach któraś reszta wynosi $0$ .

Krok 3. Wynik. Gdy reszta wynosi $0$ , mamy parę $(d, 0)$ , a $\operatorname{NWD}(d, 0) = d$ . Z kroku 1 ta liczba jest równa NWD liczb wyjściowych. $\blacksquare$

Rozszerzony algorytm i tożsamość Bézouta

Cofając się po krokach algorytmu, NWD można zapisać jako kombinację liczb wyjściowych. Z przykładu:

$18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198.$

To tożsamość Bézouta: dla dowolnych $a$ , $b$ istnieją liczby całkowite $x$ , $y$ , że $ax + by = \operatorname{NWD}(a, b)$ . Wniosek: równanie $ax + by = c$ ma rozwiązanie w liczbach całkowitych wtedy i tylko wtedy, gdy $\operatorname{NWD}(a, b)$ dzieli $c$ . Na przykład $252x + 198y = 36$ ma rozwiązanie ( $x = 8$ , $y = -10$ ), a $252x + 198y = 20$ - nie, bo $18 \nmid 20$ .

Ile trwa algorytm

Najwięcej kroków wymagają kolejne liczby Fibonacciego: dla $233$ i $144$ potrzeba $11$ dzieleń. Gabriel Lamé udowodnił w 1844 roku, że liczba dzieleń nie przekracza pięciokrotności liczby cyfr mniejszej z liczb - dla liczb stucyfrowych to najwyżej około $500$ kroków, podczas gdy rozkład na czynniki pierwsze takich liczb jest praktycznie niewykonalny.

Po co to komu

Skracanie ułamków i NWW - wspólny mianownik to NWW mianowników.
Równania diofantyczne $ax + by = c$ - rozwiązywalność i rozwiązania z tożsamości Bézouta.
Kryptografia RSA - rozszerzony algorytm Euklidesa wyznacza odwrotność modulo, potrzebną do klucza prywatnego (zob. małe twierdzenie Fermata).
Dowody w teorii liczb - z tożsamości Bézouta wynika lemat Euklidesa, a z niego podstawowe twierdzenie arytmetyki.

Kto i kiedy

Algorytm opisał Euklides w VII księdze „Elementów” (twierdzenia VII.1 i VII.2, ok. 300 r. p.n.e.), w wersji z odejmowaniem. Uchodzi za jeden z najstarszych algorytmów, które wciąż są w powszechnym użyciu. Tożsamość nosi imię francuskiego matematyka Étienne’a Bézouta (XVIII w.), choć dla liczb całkowitych znał ją już wcześniej Claude-Gaspard Bachet de Méziriac (1624).

Najczęstsze pytania

Jak obliczyć NWD algorytmem Euklidesa? Podziel większą liczbę przez mniejszą z resztą, potem dzielnik przez resztę i tak dalej, aż reszta wyniesie $0$ . Ostatnia niezerowa reszta to NWD.

Jak obliczyć NWW dwóch liczb? Podziel iloczyn liczb przez ich NWD: $\operatorname{NWW}(a, b) = \frac{ab}{\operatorname{NWD}(a, b)}$ .

Czym różni się algorytm Euklidesa od rozkładu na czynniki? Rozkład wymaga znalezienia wszystkich dzielników pierwszych, co dla dużych liczb jest bardzo trudne. Algorytm Euklidesa potrzebuje tylko dzieleń z resztą i działa szybko dla dowolnie dużych liczb.

Co to jest tożsamość Bézouta? Zapis NWD jako kombinacji liczb: $ax + by = \operatorname{NWD}(a, b)$ dla pewnych całkowitych $x$ , $y$ . Współczynniki wyznacza rozszerzony algorytm Euklidesa.

Kiedy liczby są względnie pierwsze? Gdy ich NWD wynosi $1$ - algorytm Euklidesa kończy się wtedy resztą $1$ .

Podsumowanie

$\operatorname{NWD}(a, b) = \operatorname{NWD}(b, a \bmod b)$ - dzielimy z resztą, aż reszta wyniesie zero.
Dowód: pary $(a, b)$ i $(b, r)$ mają te same wspólne dzielniki; reszty maleją, więc algorytm się kończy.
$\operatorname{NWW}(a, b) = \frac{ab}{\operatorname{NWD}(a, b)}$ .
Tożsamość Bézouta $ax + by = \operatorname{NWD}(a, b)$ ; równanie $ax + by = c$ ma rozwiązanie, gdy NWD dzieli $c$ .
Liczba kroków rośnie jak liczba cyfr (Lamé) - algorytm jest bardzo szybki.