Algorytm Euklidesa

31.10.2009 - Damian Rusak
Trudność

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 $.

$ NWW\left(a,b\right) = \frac{ab}{NWD\left(a,b\right)} $

Faktycznie, $ 180 = 36 \cdot 60 \div 12 $.

 

 

4.208335
Twoja ocena: Brak Ocena: 4.2 (24 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com