Algorytm Euklidesa

31.10.2009 - Damian Rusak

Czym jest Algorytm Euklidesa i jak taki algorytm można zapisać? Do czego służy? Jeżeli chcesz poznać odpowiedź na te pytania, zapraszamy do lektury! Ten algorytm to rzecz niezbędna dla każdego, kto chce wykorzystać w swoich programach siłę liczb.

Dwie monety - jeden problem

Nim przejdziemy do sedna sprawy, spróbujmy rozwiązać takie zadanie:

Dysponujemy monetami o dwóch nominałach - $36$ i $60$ złotych (to musi być w jakiś dawnych czasach...). Chcemy za ich pomocą wypłacić tę samą kwotę - raz tylko monetami $36$ -cio złotowymi, raz tylko $60$ -cio złotowymi. Jaka jest najmniejsza niezerowa kwota, która spełnia te wymagania?

No tak, to nie jest trudne - wystarczy chwilę pomyśleć, aby znaleźć tę kwotę - to $180$ .

Faktycznie:

$180 = 36 \cdot 5$

$180 = 60 \cdot 3$

Ale dlaczego $180$ jest najmniejszą taką liczbą? Ten przykład był prosty, występowały w nim niewielkie liczby. Ale jak znaleźć odpowiedź, gdy ktoś zapyta nas o monety o nominałach $2278$ i $2814$ ? Albo $1067$ i $582$ ? To wcale nietrudne!

Trochę matematyki

Na początek przypomnijmy kilka wiadomości z matematyki:

1. Mówimy, że liczba $d$ dzieli liczbę $n$ , jeśli istnieje taka liczba całkowita $k$ , że $n = d \cdot k$ .

Np. $3$ dzieli $12$ , gdyż $12 = 3 \cdot 4$ , a $16$ dzieli $144$ , gdyż $144 = 16 \cdot 9$ .

Fakt, że $d$ dzieli $n$ zapisujemy w ten sposób: $d \left| n$ . Mamy więc $3 \left| 12$ oraz $16 \left | 144$ . Mówimy, że jeśli $d$ dzieli $n$ , to $d$ jest dzielnikiem $n$ , a $n$ jest wielokrotnością $d$ .

Jeżeli liczba $d$ nie dzieli $n$ , będziemy pisać, że $d \nmid n$ .

2. Jeżeli liczba $d$ dzieli zarówno liczbę $a$ , jak i liczbę $b$ , to $d$ dzieli też ich różnicę, $a - b$ , oraz sumę $a + b$ .

$d\left| a\right. \: , \: d\left| b\right. \:\: \Rightarrow \: a = dn , b = dm \:\: \Rightarrow a - b = d\left(n-m\right) , \:\: a+b = d(n+m) \:\: \Rightarrow d \left| a - b \right. \: , \: d\left| a+b \right.$

Linia powyżej mówi nam, że jeśli $d$ dzieli $a$ i dzieli $b$ , to znaczy, że obie te liczby można zapisać jako iloczyn $d$ i odpowiednio $n$ oraz $m$ . W takim razie ich różnica, $a-b$ , równa jest $d\left(n-m\right)$ , a to oznacza, że ta różnica jest podzielna przez $d$ . Podobnie $a+b$ jest podzielne przez $d$ , gdyż ta suma to $d\left(n+m\right)$ .

3. Jeżeli $a$ dzieli $b$ , i $b$ dzieli $c$ , to $a$ dzieli $c$ .

$a \left| b\right. \:,\: b \left| c\right. \: \Rightarrow \:b = an \:, \: c = bm$

$\: \Rightarrow \: c = a\cdot nm \: \Rightarrow \: a\left| c \right.$

4. Jeżeli liczby $a$ i $b$ nie mają żadnego wspólnego dzielnika, większego niż jeden (czyli nie istnieje liczba większa od jeden, która dzieliłaby zarówno $a$ jaki i $b$ ), to mówimy, że te liczby są względnie pierwsze. Zapisujemy to w ten sposób : $a \bot b$ .

Na przykład $18$ i $35$ są względnie pierwsze, za to $24$ i $33$ nie są względnie pierwsze, gdyż $3 \left| 24$ oraz $3 \left| 33$ .

Najmniejsze i największe

Jaki mamy z tego pożytek? Powróćmy do przykładu z monetami o nominałach $36$ i $60$ . Szukaliśmy takiej kwoty, która byłaby podzielna zarówno przez $36$ jak i przez $60$ . To oznacza, że taka kwota musi się dzielić przez te same liczby, przez które dzielą się $36$ i $60$ . Chcemy też, aby ta liczba była jak najmniejsza.

Taką najmniejszą dodatnią liczbę, podzielną przez $a$ i przez $b$ , nazywamy najmniejszą wspólną wielokrotnością i oznaczamy przez $NWW\left(a,b\right)$ .

Jak ją wyznaczyć? Zauważmy, że wystarczy, aby $NWW\left(a,b\right)$ dzieliła się przez wszystkie dzielniki $a$ i $b$ . Chcemy otrzymać liczbę jak najmniejszą, więc nie ma sensu duplikować dzielników - jeżeli jakaś liczba $d$ dzieli zarówno $a$ jak i $b$ , ale $d^{2}$ nie dzieli obu tych liczb, to nie ma sensu, aby $NWW\left(a,b\right)$ dzieliła się przez $d^{2}$ , wystarczy aby dzieliła się przez $d$ . Stąd często $NWW\left(a,b\right) \neq a\cdot b$ .

Gdybyśmy potrafili wyznaczyć największą taką liczbę, przez którą dzielą się obie liczby $a$ i $b$ , to w łatwy sposób wyznaczylibyśmy $NWW\left(a,b\right)$ ... dlaczego?

Spójrzmy na nasz przykład - $36 = 3\cdot 12$ , $60 = 5\cdot 12$ . Widzimy, że $12$ to największy wspólny dzielnik tych dwóch liczb. W takim razie ich najmniejsza wspólna wielokrotność musi być równa $12 \cdot 3 \cdot 5$ . Dlaczego? Ponieważ $NWW\left(a,b\right)$ musi dzielić się przez $3$ (bo $36$ jest podzielne przez $3$ ), musi się też dzielić przez $5$ ( $60$ jest podzielne przez $5$ ), oraz przez $12$ - największy wspólny dzielnik $36$ i $60$ .

I to wszystko - każda liczba która dzieli $36$ oraz dzieli $60$ , dzieli też ich $NWD$ (największy wspólny dzielnik), czyli $12$ . Gdyby było inaczej, powiedzmy, że istniałaby liczba pierwsza $p$ , taka, że $p\mid a \:,\: p\mid b \:,\: p\nmid 12$ , $12$ nie byłoby $NWD\left(36,60\right)$ - wszak $12\cdot p$ jest większe niż $12$ i też dzieli obie nasze liczby.

Wiemy też, że $NWD\left(a,b\right) = NWD\left(b,a\right)$ . Dlaczego?

Wobec tego liczby $\frac{a}{NWD\left(a,b\right)}$ oraz $\frac{b}{NWD\left(a,b\right)}$ są względnie pierwsze - w $NWD\left(a,b\right)$ znajdują się wszystkie wspólne dzielniki $a$ i $b$ - gdy podzielimy $a$ i $b$ przez ich $NWD\left(a,b\right)$ , dostaniemy liczby, które nie mogą mieć wspólnego dzielnika, większego od $1$ .

Wobec tego, wymnażając $\frac{a}{NWD\left(a,b\right)}$ , $\frac{b}{NWD\left(a,b\right)}$ oraz $NWD\left(a,b\right)$ otrzymamy najmniejszą liczbę podzielną przez $a$ i przez $b$ .