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 problemNim przejdziemy do sedna sprawy, spróbujmy rozwiązać takie zadanie: No tak, to nie jest trudne - wystarczy chwilę pomyśleć, aby znaleźć tę kwotę - to . Faktycznie:
Ale dlaczego 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 i ? Albo i ? To wcale nietrudne!
Trochę matematykiNa początek przypomnijmy kilka wiadomości z matematyki: 1. Mówimy, że liczba dzieli liczbę , jeśli istnieje taka liczba całkowita , że . Np. dzieli , gdyż , a dzieli , gdyż . Fakt, że dzieli zapisujemy w ten sposób: . Mamy więc oraz . Mówimy, że jeśli dzieli , to jest dzielnikiem , a jest wielokrotnością . Jeżeli liczba nie dzieli , będziemy pisać, że .
2. Jeżeli liczba dzieli zarówno liczbę , jak i liczbę , to dzieli też ich różnicę, , oraz sumę .
Linia powyżej mówi nam, że jeśli dzieli i dzieli , to znaczy, że obie te liczby można zapisać jako iloczyn i odpowiednio oraz . W takim razie ich różnica, , równa jest , a to oznacza, że ta różnica jest podzielna przez . Podobnie jest podzielne przez , gdyż ta suma to .
3. Jeżeli dzieli , i dzieli , to dzieli .
4. Jeżeli liczby i nie mają żadnego wspólnego dzielnika, większego niż jeden (czyli nie istnieje liczba większa od jeden, która dzieliłaby zarówno jaki i ), to mówimy, że te liczby są względnie pierwsze. Zapisujemy to w ten sposób : . Na przykład i są względnie pierwsze, za to i nie są względnie pierwsze, gdyż oraz .
Najmniejsze i największe
Jaki mamy z tego pożytek? Powróćmy do przykładu z monetami o nominałach i . Szukaliśmy takiej kwoty, która byłaby podzielna zarówno przez jak i przez . To oznacza, że taka kwota musi się dzielić przez te same liczby, przez które dzielą się i . Chcemy też, aby ta liczba była jak najmniejsza. Taką najmniejszą dodatnią liczbę, podzielną przez i przez , nazywamy najmniejszą wspólną wielokrotnością i oznaczamy przez . Jak ją wyznaczyć? Zauważmy, że wystarczy, aby dzieliła się przez wszystkie dzielniki i . Chcemy otrzymać liczbę jak najmniejszą, więc nie ma sensu duplikować dzielników - jeżeli jakaś liczba dzieli zarówno jak i , ale nie dzieli obu tych liczb, to nie ma sensu, aby dzieliła się przez , wystarczy aby dzieliła się przez . Stąd często . Gdybyśmy potrafili wyznaczyć największą taką liczbę, przez którą dzielą się obie liczby i , to w łatwy sposób wyznaczylibyśmy ... dlaczego? Spójrzmy na nasz przykład - , . Widzimy, że to największy wspólny dzielnik tych dwóch liczb. W takim razie ich najmniejsza wspólna wielokrotność musi być równa . Dlaczego? Ponieważ musi dzielić się przez (bo jest podzielne przez ), musi się też dzielić przez ( jest podzielne przez ), oraz przez - największy wspólny dzielnik i . I to wszystko - każda liczba która dzieli oraz dzieli , dzieli też ich (największy wspólny dzielnik), czyli . Gdyby było inaczej, powiedzmy, że istniałaby liczba pierwsza , taka, że , nie byłoby - wszak jest większe niż i też dzieli obie nasze liczby. Wiemy też, że . Dlaczego? Wobec tego liczby oraz są względnie pierwsze - w znajdują się wszystkie wspólne dzielniki i - gdy podzielimy i przez ich , dostaniemy liczby, które nie mogą mieć wspólnego dzielnika, większego od . Wobec tego, wymnażając , oraz otrzymamy najmniejszą liczbę podzielną przez i przez . Faktycznie, .
(24 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com