Algorytm Euklidesa - NWD
Wprowadzenie
Algorytm Euklidesa to jeden z najstarszych znanych algorytmów (ok. 300 p.n.e.) służący do obliczania największego wspólnego dzielnika (NWD) dwóch liczb. Jest niezwykle efektywny i stanowi fundament wielu zastosowań w teorii liczb i kryptografii.
NWD(a, b) to największa liczba naturalna, która dzieli zarówno a, jak i b bez reszty.
Algorytm Euklidesa jest wykorzystywany w:
- Upraszczaniu ułamków (redukcja do najprostszej postaci)
- Kryptografii (algorytm RSA, generowanie kluczy)
- Teorii liczb (liczby względnie pierwsze)
- Obliczaniu NWW (najmniejszej wspólnej wielokrotności)
- Rozwiązywaniu równań diofantycznych
- Algebrze liniowej (diagonalizacja macierzy)
Przykłady: - NWD(48, 18) = 6 - NWD(100, 35) = 5 - NWD(17, 19) = 1 (liczby względnie pierwsze)
Podstawy teoretyczne
Definicja NWD
Największy wspólny dzielnik liczb a i b to:
NWD(a, b) = max{d : d|a ∧ d|b}
Gdzie d|a oznacza "d dzieli a".
Własności NWD
1. NWD(a, b) = NWD(b, a) (przemienność)
2. NWD(a, 0) = a (przypadek bazowy)
3. NWD(a, b) = NWD(b, a mod b) (kluczowa własność!)
4. NWD(a, b) = NWD(a-b, b) (wersja odejmowania)
5. NWD(ka, kb) = k × NWD(a, b) (liniowość)
Kluczowa obserwacja Euklidesa
Lemat: Jeśli a = b × q + r (gdzie q to iloraz, r to reszta), to:
NWD(a, b) = NWD(b, r)
Intuicja: Wspólne dzielniki (a, b) są takie same jak wspólne dzielniki (b, r).
Przykład:
NWD(48, 18) = NWD(18, 48 mod 18) = NWD(18, 12)
= NWD(12, 18 mod 12) = NWD(12, 6)
= NWD(6, 12 mod 6) = NWD(6, 0)
= 6
Implementacje algorytmu
1. Wersja iteracyjna (klasyczna)
Wyjście:
=== NWD - wersja iteracyjna ===
a b NWD(a,b)
-----------------------------------
48 18 6
100 35 5
17 19 1
1071 462 21
0 5 5
12 12 12
2. Wersja rekurencyjna
Wyjście:
=== NWD - wersja rekurencyjna ===
NWD(48, 18) = 6
NWD(252, 105) = 21
NWD(1071, 1029) = 21
3. Wizualizacja kroków algorytmu
Wyjście:
=== NWD - wizualizacja kroków ===
Obliczanie NWD(1071, 462):
Krok a b a mod b
---------------------------------------------
1 1071 462 147
2 462 147 21
3 147 21 0
Wynik: NWD = 21
Obliczanie NWD(48, 18):
Krok a b a mod b
---------------------------------------------
1 48 18 12
2 18 12 6
3 12 6 0
Wynik: NWD = 6
4. Algorytm Euklidesa przez odejmowanie
Wersja pierwotna (mniej efektywna, ale prostsza koncepcyjnie):
Wyjście:
=== NWD - wersja przez odejmowanie ===
NWD(48, 18) = 6
NWD(100, 35) = 5
NWD(21, 14) = 7
Rozszerzony algorytm Euklidesa
Rozszerzony algorytm Euklidesa znajduje nie tylko NWD(a, b), ale także współczynniki x, y takie, że:
a × x + b × y = NWD(a, b)
To równanie nazywamy tożsamością Bézouta.
Implementacja
Wyjście:
=== Rozszerzony algorytm Euklidesa ===
a b NWD x y Sprawdzenie: a×x + b×y
----------------------------------------------------------------------
48 18 6 1 -2 48×1 + 18×-2 = 6
100 35 5 2 -5 100×2 + 35×-5 = 5
17 19 1 9 -8 17×9 + 19×-8 = 1
240 46 2 -9 47 240×-9 + 46×47 = 2
Zastosowania algorytmu Euklidesa
1. Upraszczanie ułamków
Wyjście:
=== Upraszczanie ułamków ===
Ułamek Uproszczony NWD
---------------------------------------------
48/18 8/3 6
100/35 20/7 5
24/60 2/5 12
7/13 7/13 1
144/256 9/16 16
2. Sprawdzanie liczb względnie pierwszych
Liczby względnie pierwsze: NWD(a, b) = 1
Wyjście:
=== Liczby względnie pierwsze ===
a b NWD Względnie pierwsze?
---------------------------------------------
15 28 1 TAK
21 35 7 NIE
17 19 1 TAK
100 101 1 TAK
12 18 6 NIE
3. Odwrotność modulo (dla kryptografii)
Wyjście:
=== Odwrotność modulo ===
a m a⁻¹ mod m Sprawdzenie: (a × a⁻¹) mod m
------------------------------------------------------------
3 11 4 (3 × 4) mod 11 = 1
5 17 7 (5 × 7) mod 17 = 1
7 26 15 (7 × 15) mod 26 = 1
4. Najmniejsza wspólna wielokrotność (NWW)
Wyjście:
=== Najmniejsza wspólna wielokrotność (NWW) ===
a b NWD NWW Sprawdzenie: NWD × NWW
------------------------------------------------------------
12 18 6 36 12×18 = 6×36 = 216
4 6 2 12 4×6 = 2×12 = 24
21 14 7 42 21×14 = 7×42 = 294
15 25 5 75 15×25 = 5×75 = 375
NWD dla wielu liczb
Wyjście:
=== NWD i NWW dla wielu liczb ===
Liczby: [12, 18, 24]
NWD = 6
NWW = 72
Liczby: [10, 15, 20, 25]
NWD = 5
NWW = 300
Liczby: [48, 64, 80, 96]
NWD = 16
NWW = 960
Złożoność obliczeniowa
Analiza algorytmu Euklidesa
Twierdzenie Lamé (1844): Liczba kroków algorytmu Euklidesa dla liczb a, b jest proporcjonalna do liczby cyfr w mniejszej liczbie.
Złożoność: O(log min(a, b))
Najgorszy przypadek
Najgorszy przypadek występuje dla kolejnych liczb Fibonacciego:
Wyjście:
=== Najgorszy przypadek - liczby Fibonacciego ===
F(n) F(n+1) Kroki NWD
---------------------------------------------
1 1 1 1
1 2 2 1
2 3 2 1
3 5 3 1
5 8 3 1
8 13 4 1
13 21 4 1
21 34 5 1
34 55 5 1
55 89 6 1
89 144 6 1
Porównanie implementacji
Wyjście (przykładowe):
=== Benchmark algorytmów NWD ===
a b Algorytm Czas (μs) Wynik
--------------------------------------------------------------------------------
1071 462 Iteracyjna 0.87 21
1071 462 Rekurencyjna 1.23 21
1071 462 Przez odejmowanie 42.15 21
123456 789012 Iteracyjna 1.12 12
123456 789012 Rekurencyjna 1.56 12
123456 789012 Przez odejmowanie --- (pominięto)
987654321 123456789 Iteracyjna 1.89 9
987654321 123456789 Rekurencyjna 2.34 9
987654321 123456789 Przez odejmowanie --- (pominięto)
Podsumowanie
Kluczowe własności
✅ Złożoność: O(log min(a, b)) - bardzo wydajny ✅ Prostota: Łatwa implementacja (iteracyjna i rekurencyjna) ✅ Fundamentalność: Podstawa wielu algorytmów w teorii liczb ✅ Deterministyczność: Zawsze poprawny wynik
Wersje algorytmu
| Wersja | Złożoność | Zastosowanie |
|---|---|---|
| Iteracyjna (modulo) | O(log n) | Standardowa, najszybsza |
| Rekurencyjna (modulo) | O(log n) | Elegancka, dydaktyczna |
| Przez odejmowanie | O(n) | Wolna, historyczna |
| Rozszerzona | O(log n) | Kryptografia, równania diofantyczne |
Zastosowania
✅ Upraszczanie ułamków: Redukcja do najprostszej postaci ✅ NWW: Obliczanie najmniejszej wspólnej wielokrotności ✅ Kryptografia: Algorytm RSA, generowanie kluczy ✅ Liczby względnie pierwsze: Test NWD(a,b) = 1 ✅ Odwrotność modulo: Rozszerzony algorytm Euklidesa
Co dalej?
Po opanowaniu algorytmu Euklidesa, następne kroki to:
- Lekcja 68: NWD i NWW - zastosowania
- Praktyczne problemy z NWD i NWW
- Zaawansowane techniki
-
Przykłady z życia codziennego
-
Lekcja 69: Rozkład na czynniki pierwsze
- Faktoryzacja liczb
- Algorytmy rozkładu
-
Związek z NWD
-
Lekcja 70: Liczby doskonałe
- Definicja i własności
- Algorytmy znajdowania
- Teoria liczb
Zadania praktyczne
Zadanie 1: NWD trzech liczb
Napisz efektywną funkcję obliczającą NWD(a, b, c) dla trzech liczb.
Zadanie 2: Sekwencja Euklidesa
Dla danej pary (a, b) wyświetl wszystkie pary otrzymane w algorytmie Euklidesa.
Zadanie 3: Równanie diofantyczne
Rozwiąż równanie ax + by = c używając rozszerzonego algorytmu Euklidesa.
Zadanie 4: Ułamek łańcuchowy
Przedstaw wynik dzielenia a/b jako ułamek łańcuchowy używając kroków algorytmu Euklidesa.
Zadanie 5: Kalkulator modulo
Stwórz kalkulator wykonujący działania arytmetyczne modulo m (dodawanie, odejmowanie, mnożenie, dzielenie z użyciem odwrotności modularnej).
Następna lekcja: NWD i NWW - zastosowania praktyczne