Antoni M. Zajączkowski: Algorytmy i podstawy programowania  największy wspólny dzielnik
5 kwietnia 2009
NAJWI
KSZY WSPÓLNY DZIELNIK
DEFINICJA. Liczba całkowita d jest dzielnikiem (divisor) liczby całkowitej m , wtedy i
tylko wtedy, gdy m jest całkowitą wielokrotnością d .
Inaczej mówiąc, dla pewnej liczby k " spełnione jest równanie
m = d ·k .
Ponieważ "d " : 0 = d · 0, wiÄ™c każda liczba caÅ‚kowita jest dzielnikiem zera. StÄ…d wy-
nika, że zero ma nieskończoną liczbę dzielników.
Nietrudno widzieć, że jeżeli d jest dzielnikiem liczby m , to jest też dzielnikiem liczby
-m . Z tego wnioskujemy, że dzielniki liczb m i -m są takie same. Poza tym, d " jest
dzielnikiem m " , wtedy i tylko wtedy, gdy -d jest dzielnikiem m . W zwiÄ…zku z tym,
dalsze rozważania można ograniczyć do nieujemnych liczb całkowitych.
Niech m 0 i m = d ·k dla pewnych d k " . Ponieważ d = m k , wiÄ™c
|d |= m |k |d"m , -m d"d d"m . (*)
Pokazaliśmy, że wszystkie dzielniki liczby m 0 należą do przedziału [-m m].
DEFINICJA. Wspólnym dzielnikiem (common divisor) liczb m i n nazywamy liczbę
całkowitą, która jest jednocześnie dzielnikiem m i n .
Zauważmy, że liczby -1 i 1 są wspólnymi dzielnikami każdej liczby całkowitej.
Jeżeli m n " nie są równocześnie równe zeru, czyli prawdziwe jest zdanie
m 0orn 0 ,
to zgodnie z (*) mogą mieć tylko skończoną liczbę wspólnych dzielników.
DEFINICJA. Największym wspólnym dzielnikiem (greatest common divisor) liczb m n ,
z których co najmniej jedna jest różna od zera, nazywamy największy z ich wspólnych
dzielników. Oznaczamy go NWD(m n), albo GCD(m n).
Możemy teraz zająć się problemem obliczania NWD(m n), czyli opracowaniem algo-
rytmu wyznaczajÄ…cego NWD(m n).
Pierwszy algorytm znamy z matematyki elementarnej
1. Rozłożyć liczby | m | i | n | na czynniki pierwsze,
2. Znalez
ć najwyższe potęgi czynników pierwszych, które są wspólnymi dzielnikami
| m | i | n |,
3. Znalez
ć iloczyn tych potęg, co daje NWD(m n).
Przykład. Obliczmy NWD(135 300) wg tego algorytmu.
Rozkład na czynniki pierwsze jest następujący:
135 = 1· 3· 3· 3· 5, 300 = 1·2·2· 3· 5· 5 .
Dzielnikami tych liczb sÄ…
135 : Ä…1 Ä…3 Ä…5 Ä…9 Ä…15 Ä…27 Ä…45 Ä…135 ,
300 : Ä…1 Ä…2 Ä…3 Ä…5 Ä…4 Ä…6 Ä…10 Ä…12 Ä…15 Ä…20 Ä…25 Ä…30 Ä…60 Ä…75 Ä…100 Ä…150 Ä…300 ,
a wspólnymi dzielnikami
3 5 15 i stÄ…d NWD(135 300) = 31 · 51 = 15 .
Zauważmy, że ten algorytm wyznaczania NWD wymaga rozkładu argumentów na czyn-
niki pierwsze, co w przypadku dużych liczb znacznie wydłuża działanie algorytmu.
Zajmijmy się więc inną metodą, która nie wymaga kosztownego wyznaczania rozkładu na
czynniki pierwsze.
Na początku zauważmy, że jeżeli prawdziwe jest zdanie
m = 0xorn = 0 ,
czyli dokładnie jedna z liczb jest równa zeru, to
1
Antoni M. Zajączkowski: Algorytmy i podstawy programowania  największy wspólny dzielnik
5 kwietnia 2009
NWD(m n) = Max(|m | |n |),
natomiast, gdy obydwie te liczby są różne od zera, czyli spełniają warunek
m 0andn 0 ,
to musi zachodzić nierówność
0 Stąd wynika, że w tym ostatnim przypadku możemy wykonać obliczenia w pętli while, za-
czynajÄ…c od
t = Min(| m | |n |)
i sprawdzenia czy liczba ta dzieli bez reszty | m | i | n |. Jeżeli tak jest, to t = NWD(m n) i
algorytm się kończy. W przeciwnym przypadku zmniejszamy t o 1 i przeprowadzamy test
dzielenia bez reszty liczb | m | | n |. Ten krok powtarzamy tak długo, aż obydwie reszty z
dzielenia będą równe zeru. W najgorszym przypadku otrzymamy NWD(m n) = 1, ponieważ
1 jest dzielnikiem każdej liczby całkowitej.
Opisany algorytm wyznaczania NWD nazywany bezpośrednim, a Sedgewick (1983) na-
zywa go siłowym (brute force).
Zadanie. Ile razy wykonywana jest pętla while, w przypadku, gdy liczby m n są
względnie pierwsze i żadna z nich nie jest równa zeru.
Zadanie obliczeniowe 1. Napisać, uruchomić i przetestować program w języku Ada
wyznaczający NWD wg podanego algorytmu bezpośredniego. W przypadku, gdy dane wej-
ściowe m n " są zerowe, należy ten przypadek wyróżnić komunikatem "NWD
nieokreslony" i nie wykonywać głównej ścieżki algorytmu. Oprócz NWD wyznaczyć liczbę
wykonań pętli.
Algorytm bezpośredni nie opiera się na kosztownym rozkładzie argumentów na czynniki
pierwsze, ale liczba powtórzeń pętli while w przypadku dużych wartości danych wejścio-
wych jest wielka (patrz Zadanie). Znacznie efektywniejszy jest algorytm Euklidesa
(Courant, Robbins, 1967: Ross, Wright, 2000), który oparty jest na następującym wyniku:
TWIERDZENIE (Ross, Wright, 2000, 259). Jeżeli liczby m n " i n 0 , to wspólne
dzielniki tych liczb są takie same jak wspólne dzielniki liczb n i mmodn , co zapisujemy w
postaci
NWD(m n) = NWD(n mmodn). (**)
Dowód: (Ross, Wright, 2000, 258).
Przykład. Zastosować to twierdzenie do wyznaczenia NWD następujących liczb (45 12) i
(135 300).
NWD(45 12) = NWD(12 45mod12)
= NWD(12 9) = NWD(9 12mod9)
= NWD(9 3) = NWD(3 9mod3)
= NWD(3 0) = 3
NWD(135 300) = NWD(300 135mod300)
= NWD(300 135) = NWD(135 300mod135)
= NWD(135 30) = NWD(30 135mod30)
= NWD(30 15) = NWD(15 30mod15)
= NWD(15 0) = 15
Przy implementacji komputerowej algorytmu Euklidesa warto zauważyć, że reszta z
dzielenia spełnia nierówność
2
Antoni M. Zajączkowski: Algorytmy i podstawy programowania  największy wspólny dzielnik
5 kwietnia 2009
0 d"mmodn oraz
NWD(m n) = NWD(n m), NWD(m n) = NWD(| m | | n |).
W związku z tym, dogodnie jest zdefiniować zmienne pomocnicze
a = Max(| m | |n |), b = Min(|m | |n |),
które spełniają warunki a e"b i NWD(m n) = NWD(a b).
Obliczenia wykonujemy przy pomocy pętli while, której test wejściowy jest relacją b 0 .
Wewnątrz pętli stosujemy podane twierdzenie, czyli NWD(a b) = NWD(b amodb) i odpo-
wiednio wymieniamy zmienne. Powtarzamy ten proces tak długo, aż reszta z dzielenia stanie
się równa zeru.
Nietrudno widzieć, że tak robiliśmy w ostatnim przykładzie, przy czym deklaracja zmiennych
a b wg podanych wzorów pozwala na pominięcie pierwszych dwóch operacji wykonanych
przy wyznaczaniu NWD(135 300).
To, że algorytm Euklidesa wyznacza NWD(m n) potwierdza
TWIERDZENIE. Algorytm Euklidesa daje w wyniku NWD liczb całkowitych m n takich,
że m 0orn 0 .
Dowód: (Ross, Wright, 2000, 260).
Liczbę przebiegów pętli while w tym algorytmie można oszacować stosując
TWIERDZENIE. Dla danych liczb całkowitych m n e" 0 algorytm Euklidesa wyznacza-
nia NWD(m n) wykonuje co najwyżej
2log2(m +n) (#)
przebiegów pętli.
Dowód: (Ross, Wright, 2000, 260).
Zadanie obliczeniowe 2. Napisać, uruchomić i przetestować program w języku Ada
wyznaczający NWD wg podanego algorytmu Euklidesa. W przypadku, gdy dane wejściowe
m n " są zerowe, należy ten przypadek wyróżnić komunikatem "NWD nieokreslony" i nie
wykonywać głównej ścieżki algorytmu. Oprócz NWD wyznaczyć liczbę wykonań pętli i po-
równać z oszacowaniem (#).
LITERATURA
Courant, R. i H. Robbins. (1967). Co to jest matematyka. PWN, Warszawa (tłum. z ang.).
Ross, K.A i C.R.B. Wright. (2000). Matematyka dyskretna. PWN, Warszawa (tłum. z ang.).
Sedgewick, R. (1983). Algorithms. Addison-Wesley, Reading, Massachussets.
3