Wersja z 2019-05-21
Matematyka to nauka, która powstała jako odpowiedź na wyzwania codzienności. Choć dziś wydaje się bardzo abstrakcyjna, a nawet nieużyteczna, w rzeczywistości jest głęboko praktyczna. Właśnie dlatego ciągle stosowaliśmy całą zdobytą już wiedzę o ułamkach do rozwiązywania życiowych problemów pana Kowalskiego czy pani Malinowskiej.
Czasem jednak bywa i tak, że warto opanować umiejętności, które bezpośrednio nie znajdują zastosowania w praktyce (a przynajmniej można się bez nich obyć). Umiejętności te okazują się jednak przydatne na późniejszych etapach.
Przyszedł czas, by opanować taką właśnie umiejętność. Umiejętność obliczania największego wspólnego dzielnika, oznaczanego u nas skrótem NWD, a w literaturze anglojęzycznej gcd (great common divisor), pozwala szybko sprowadzać ułamek do postaci nieskracalnej, a poza tym pozwala odpowiedzieć na pytanie, przez ile należy ułamek skrócić, aby doprowadzić do najprostszej, nieskracalnej postaci.
Piszemy `a | b`, co odczytujemy `a` jest dzielnikiem `b`, jeśli wiemy, że `b` dzieli się przez `a` bez reszty. Na przykład `2 | 10` – dwa jest dzielnikiem dziesięciu, `5 | 10` – pięć jest dzielnikiem dziesięciu, `15 | 60` – piętnaście jest dzielnikiem sześćdziesięciu.
Jeśli `a | b` i `a | c`, to mówimy, że `a` jest wspólnym dzielnikiem `b` i `c`. Na przykład `15 | 60` i `15 | 90` – piętnaście jest wspólnym dzielnikiem sześćdziesięciu i dziewięćdziesięciu. Zauważmy jednak, że także `5 | 60` i `5 | 90` – pięć jest wspólnym dzielnikiem sześćdziesięciu i dziewięćdziesięciu. Takich wspólnych dzielników znajdziemy jeszcze kilka.
Poszukiwać będziemy teraz największego wspólnego dzielnika dwóch liczb. Wiemy już, że wspólnymi dzielnikami liczb 60 i 90 są na przykład 15 i 5. Oczywiście 15 jest większe od 5.
Czy jednak istnieje jeszcze większa liczba, która jest wspólnym dzielnikiem 60 i 90?
Aby to ustalić, rozłożymy obie liczby na czynniki, a dokładniej mówiąc, rozłożymy je na czynniki pierwsze. Przecież wiemy, że na przykład `60 = 15 * 4` – oto udało nam się rozłożyć 60 na czynniki. Nie o taki rozkład jednak nam chodzi. Okazuje się bowiem, że zarówno 15, jak i 4, udaje się rozłożyć na czynniki prostsze, a przy tym większe od jedności; przecież `15 = 3 * 5`, a `4 = 2 * 2`. Zatem ostatecznie `60 = 2 * 2 * 3 * 5` – i właśnie o taki rozkład nam chodziło. Bowiem żadna z występujących tu liczb: 2, 3, 5, nie dzieli się już przez żadną inną liczbę z wyjątkiem 1 i siebie samej.
Takie liczby jak 2, 3, 5, 7, 11, 13, 17, 19, … mające tylko dwa dzielniki naturalne: jeden i siebie samą, nazywamy liczbami pierwszymi. Liczby naturalne, które dadzą się rozłożyć na liczby pierwsze, nazywamy złożonymi. Liczby 0 i 1 nie są ani pierwsze, ani złożone. Nie da się odgadnąć, czy dana liczba jest pierwsza, nie ma też żadnej metody, która pozwalałaby to obliczyć. Trzeba to po prostu sprawdzić, próbując dzielić daną liczbę kolejno przez wszystkie liczby pierwsze od niej mniejsze. Mówiąc dokładniej, sprawdzamy liczby pierwsze aż do liczby, której kwadrat jest większy od danej. Na przykład aby sprawdzić liczbę 29, próbujemy ją (bezskutecznie) podzielić przez 2, 3, 5, i tyle wystarczy, bo kwadrat kolejnej liczby pierwszej, 7, czyli 49, jest już większy od 29 (wniosek: 29 to liczba pierwsza).
Rozłóżmy jeszcze 90 na czynniki pierwsze. Możemy na przykład napisać, że `90 = 9 * 10`, co przecież jest oczywiste. Ale `9 = 3 * 3`, zaś `10 = 2 * 5`, dlatego ostatecznie `90 = 2 * 3 * 3 * 5`.
Poszukajmy teraz największego wspólnego dzielnika obu liczb. Jeśli nasze liczby tworzą ułamek, będzie to największa liczba, przez którą ten ułamek można skrócić. W tym celu trzeba znaleźć te czynniki pierwsze, które się powtarzają w rozkładzie obu liczb. Widać, że powtarzają się dwójki, trójki i piątki – jednak ta informacja nie wystarczy, musimy jeszcze wiedzieć, ile dwójek, trójek i piątek się powtarza. W rozkładzie liczby 60 występują dwie dwójki, ale w rozkładzie liczby 90 tylko jedna – zatem powtarza się tylko jedna dwójka. Podobnie zauważamy, że powtarza się jedna trójka oraz jedna piątka. Największy wspólny dzielnik liczb 60 i 90 to zatem `2 * 3 * 5 = 30`. Możemy to zapisać symbolicznie: `NWD(60,90) = 30`.
Z obliczeń tych wynika, że aby otrzymać ułamek nieskracalny, należy `60/90` skrócić przez 30. Otrzymamy wówczas `2/3`.
W praktyce szkolnej rozkładu na czynniki dokonujemy w sposób bardziej systematyczny, korzystając ze schematu, w którym będziemy sprawdzać dzielniki kolejno. Piszemy rozkładaną liczbę, a na prawo od niej stawiamy pionową kreskę. Sprawdzamy, czy liczba dzieli się przez 2. Jeśli tak, piszemy 2 na prawo od kreski, jeśli nie, sprawdzamy kolejną liczbę pierwszą, czyli 3, i tak dalej aż do skutku (przypomnijmy, że do liczb pierwszych należą 2, 3, 5, 7, 11, 13, 17, 19, …). Następnie dzielimy liczbę przez wypisany dzielnik, a wynik dzielenia zapisujemy pod liczbą. Teraz przedłużamy w dół kreskę z prawej i szukamy następnego dzielnika, zaczynając od tego, którego użyliśmy ostatnio (jeśli było to 2, to zaczynamy od 2, jeśli było to 3, to od 3 itd.). Metoda ta jest niezawodna pod warunkiem, że nie popełniliśmy błędu i nie ominęliśmy poprzednio jakiegoś dzielnika – jeśli tak się stało, zaczynamy sprawdzać podzielność od 2. Kontynuujemy tak długo, aż w wyniku otrzymamy 1. Kolumna liczb na prawo od kreski to czynniki pierwsze, na które rozkłada się początkowa liczba, w dodatku już poukładane według wielkości (o ile nie zgubiliśmy jakiegoś dzielnika po drodze).
Aby znaleźć NWD dwóch liczb, rozkładamy te liczby na czynniki, a następnie wyszukujemy w rozkładzie czynników, które się powtarzają – możemy je podkreślić albo zaznaczyć gwiazdką. Pozostaje nam wówczas już tylko wymnożyć te czynniki (oczywiście w jednej kopii). Praktyczniej jest zacząć mnożenie od dołu, bo wówczas najtrudniejsze mnożenia (największych liczb) wykonujemy jako pierwsze.
Sprawdźmy teraz opisaną metodą, przez jaką liczbę należy skrócić ułamek `1260/2100`, aby otrzymać ułamek nieskracalny. Poniższa tabele przedstawiają kolejne etapy obliczeń.
1260 |
1260 | 2 630 |
1260 | 2 630 | 2 315 |
1260 | 2 630 | 2 315 | 3 105 |
1260 | 2 630 | 2 315 | 3 105 | 3 35 |
1260 | 2 630 | 2 315 | 3 105 | 3 35 | 5 7 |
1260 | 2 630 | 2 315 | 3 105 | 3 35 | 5 7 | 7 1 |
| a | b | c | d | e | f | g |
|
2100 |
2100 | 2 1050 |
2100 | 2 1050 | 2 525 |
2100 | 2 1050 | 2 525 | 3 175 |
2100 | 2 1050 | 2 525 | 3 175 | 5 35 |
2100 | 2 1050 | 2 525 | 3 175 | 5 35 | 5 7 |
2100 | 2 1050 | 2 525 | 3 175 | 5 35 | 5 7 | 7 1 |
| a | b | c | d | e | f | g |
|
1260 | 2 2100 | 2 630 | 2 1050 | 2 315 | 3 525 | 3 105 | 3 175 | 5 35 | 5 35 | 5 7 | 7 7 | 7 1 1 |
1260 | 2 2100 | 2 630 | 2 1050 | 2 315 | 3 525 | 3 105 | 3 175 | 5 35 | 5 35 | 5 7 | 7 7 | 7 1 1 |
1260 | 2 2100 | 2 630 | 2 1050 | 2 315 | 3 525 | 3 105 | 3 175 | 5 35 | 5 35 | 5 7 | 7 7 | 7 1 1 |
1260 | 2 2100 | 2 630 | 2 1050 | 2 315 | 3 525 | 3 105 | 3 175 | 5 35 | 5 35 | 5 7 | 7 7 | 7 1 1 |
1260 | 2 2100 | 2 630 | 2 1050 | 2 315 | 3 525 | 3 105 | 3 175 | 5 35 | 5 35 | 5 7 | 7 7 | 7 1 1 |
| a | b | c | d | e |
|
Pozostaje jeszcze wymnożyć pod spodem zaznaczone czynniki, zaczynając od największych: `NWD(1260,2100) = 2 * 2 * 3 * 5 * 7 = 2 * 2 * 3 * 35 = 2 * 2 * 105 = 2 * 210 = 420`. Możemy jeszcze także przyjrzeć się czynnikom, które nie są wspólne; utworzą one ułamek nieskracalny. W rozkładzie 1260 niezaznaczony został tylko czynnik 3, zaś w rozkładzie 2100 – czynnik 5.
Odpowiedź: aby ułamek `1260/2100` doprowadzić do postaci nieskracalnej, należy skrócić go przez 420. Wynikiem skrócenia jest ułamek `3/5`.
Poznamy teraz kolejną, podobną, ale nieco szybszą metodę znajdowania NWD, o której nie wiadomo dlaczego milczą szkolne podręczniki. Nic nie stoi na przeszkodzie, by metodę tę opanować na swój własny użytek – mądry nauczyciel z pewnością to doceni i wynagrodzi. Okaże się także, że obliczanie NWD może mieć całkiem praktyczne zastosowania.
Sierżant Bąk dowodzi oddziałem złożonym z 60 żołnierzy. Otrzymał właśnie 140 bochenków chleba, które muszą wystarczyć jego ludziom na czas kilkudniowej akcji na poligonie. Aby zapewnić sprawiedliwą i jednocześnie bardzo sprawną dystrybucję zaopatrzenia, zamierza podzielić oddział na kilkuosobowe grupy, i każdej grupie wręczyć pakunek z chlebem. Ile pakunków musi przygotować służba zaopatrzenia? Ile osób będzie liczyć każda z grup? Ile bochenków chleba znajdzie się w każdym pakunku? Ile chleba przypadnie na jednego żołnierza?
Problem sierżanta Bąka sprowadza się do znalezienia największego wspólnego dzielnika liczb 140 i 60, a następnie do maksymalnego skrócenia ułamka `140/60`. Zamiast rozkładać osobno każdą z liczb 140 i 60, sierżant postanowił rozłożyć je jednocześnie. W tym celu musi wypisać obie liczby obok siebie, rozdzielając je przecinkiem, a na prawo narysować pionową kreskę jak w poprzedniej metodzie. Teraz będzie wypisywać kolejne dzielniki choćby tylko jednej z pary liczb. Jeśli obie liczby dzielą się przez dany dzielnik, podzieli każdą z liczb. Jeśli dana liczba pierwsza jest dzielnikiem tylko jednej z liczb, postawi obok dzielnika gwiazdkę i podzieli tylko tę liczbę, którą można, natomiast drugą przepisze bez zmian. Gwiazdkę napisze także przy dzielonej liczbie. Obliczenia będzie prowadził tak długo, aż otrzyma dwie jedynki.
Kolejne etapy rachunku będą wyglądać tak:
140, 60 |
140, 60 | 2 70, 30 |
140, 60 | 2 70, 30 | 2 35, 15 |
140, 60 | 2 70, 30 | 2 35, *15 | 3* 35, 5 |
140, 60 | 2 70, 30 | 2 35, *15 | 3* 35, 5 | 5 7, 1 |
140, 60 | 2 70, 30 | 2 35, *15 | 3* 35, 5 | 5 *7, 1 | 7* 1, 1 |
| a | b | c | d | e | f |
|
Obliczamy NWD, mnożąc tylko czynniki bez gwiazdki: `NWD(140,60) = 2 * 2 * 5 = 2 * 10 = 20`.
Ułamek po skróceniu możemy obliczyć, dzieląc licznik 140 i mianownik 60 przez 20. Jeśli jednak robiliśmy gwiazdki także przy liczbach, nie tylko przy czynnikach rozkładu, wystarczy odszukać teraz te liczby. W rozkładzie liczby 140 gwiazdka jest tylko przy wartości 7. Na tej samej wysokości na prawo od kreski znajduje się czynnik 7. To właśnie będzie licznik ułamka nieskracalnego. W rozkładzie mianownika 60 gwiazdka jest przy wartości 15, a na tej samej wysokości na prawo od kreski znajduje się czynnik 3 – to będzie mianownik ułamka nieskracalnego.
Ostatecznie zatem `140/60 = 7/3`. Możemy jeszcze wyłączyć całości: `140/60 = 7/3 = 2 1/3`.
Pomyślmy teraz, jak zinterpretować otrzymane wartości i tym samym jakich udzielić odpowiedzi. Otóż największy wspólny dzielnik to nic innego jak liczba grup żołnierzy (i jednocześnie liczba pakunków, które trzeba przygotować). Równość `140/60 = 7/3` odczytujemy tak: 140 bochenków chleba przypada na 60 żołnierzy w całym oddziale. W każdej grupie natomiast 7 bochenków chleba przypada na 3 żołnierzy. Końcowa liczba mieszana oznacza, ile chleba przypadnie na jednego żołnierza.
Odpowiedzi będą więc następujące. Służba zaopatrzenia musi przygotować 20 pakunków. Każda z grup będzie liczyła 3 żołnierzy. W każdym pakunku znajdzie się 7 bochenków chleba. Na każdego żołnierza przypadnie po dwa i jedna trzecia bochenka chleba.
Dwie liczby są względnie pierwsze, jeśli w ich rozkładach na czynniki pierwsze żaden czynnik nie występuje u obu jednocześnie. Np. 10 i 21 są względnie pierwsze, bo 10 = 2 · 5, a 21 = 3 · 7. W takim wypadku największy wspólny dzielnik równy jest 1. Ułamek, którego licznik i mianownik stanowią liczby względnie pierwsze, jest nieskracalny.
Omówione dotąd metody znajdowania największego wspólnego dzielnika wymagały rozkładu liczby na czynniki pierwsze. Nie zawsze jest to dobre rozwiązanie, zwłaszcza gdy liczby są dość duże i gdy są iloczynem większych licz pierwszych.
Spróbujmy na przykład znaleźć `NWD(986,748)`. Rozkład mniejszej z liczb nie jest trudny: `748 = 2 * 374 = 2 * 2 * 187`. Wystarczy teraz zauważyć, że `187` dzieli się przez `11`, a rozkład będzie gotowy: `748 = 2 * 374 = 2 * 2 * 187 = 2 * 2 * 11 * 17`.
Jednak rozkład `986` nie okazuje się już taki prosty. Krok `986 = 2 * 493` jest oczywiście trywialny. Co jednak zrobić z `493`? Trzeba po kolei sprawdzać liczby pierwsze, aż w końcu dojdziemy do właściwej (`17`). Rzeczywiście, nie jest to jak widać najłatwiejszy sposób.
Na szczęście już Euklides opracował algorytm, który pozwala znaleźć największy wspólny dzielnik bez rozkładu na czynniki pierwsze. Metoda ta sprawdza się właśnie w takich bardziej skomplikowanych przypadkach, jak `NWD(986,748)`.
Otóż okazuje się, że wartość największego wspólnego dzielnika nie ulegnie zmianie, jeśli zamiast większej z liczb weźmiemy różnicę obu liczb. Uzasadnienie pozostawiamy czytelnikom, tu spróbujemy natomiast zastosować tę metodę w omawianym przypadku.
Mamy zatem `986 - 748 = 238`, piszemy więc `NWD(986,748) = NWD(748,238)`. Zmniejszyliśmy liczby, co niewątpliwie ułatwi nam zadanie.
Nic nie szkodzi, by zabieg powtórzyć jeszcze raz: `748 - 238 = 510`. Wnioskujemy z tego, że `NWD(986,748) = NWD(510,238)` (różnicą zastępujemy zawsze większą z liczb). Zauważmy jednak, że od różnicy możemy jeszcze raz odjąć tę samą liczbę: `510 - 238 = 272`, otrzymując `NWD(986,748) = NWD(272,238)`. Nic nie stoi na przeszkodzie, by operację tę powtórzyć po raz trzeci: `272 - 238 = 34`, co daje nam `NWD(986,748) = NWD(238,34)`.
Możemy teraz odejmować `34` od `238` i operację tę powtarzać, otrzymując kolejno `204, 170, 136, 102, 68, 34`, co ostatecznie doprowadzi nas do konkluzji, że `NWD(986,748) = NWD(34,34)`. A cóż jest największym wspólnym dzielnikiem dwóch takich samych liczb? Oczywiście NWD jest równy każdej z nich, czyli tutaj `34`. Zadanie wykonane: `NWD(986,748) = 34`.
Algorytm ten możemy znacząco przyśpieszyć, stosując dzielenie z resztą zamiast odejmowania. Ponieważ istotna będzie reszta z dzielenia, a nie iloraz, kalkulatora musimy używać umiejętnie.
W omawianym przypadku możemy zacząć od dzielenia `986 : 748`, które daje (w okienku kalkulatora) `1.31818181…`. Wynik ten nic nam nie dał, i tak musimy odjąć obie liczby (do czego rzecz jasna możemy także użyć kalkulatora): `986 - 748 = 510`. Mamy więc jak poprzednio `NWD(986,748) = NWD(510,238)`.
Teraz jednak kalkulator okaże się bardziej przydatny. Obliczamy `510 : 238 = 2.142857143…`, od wyniku odejmujemy całości, czyli `2`, i otrzymaną liczbę `0.142857143…` mnożymy przez `238`, co daje nam ostatecznie szukaną resztę `34`. Na tym etapie otrzymujemy więc, że `NWD(986,748) = NWD(238,34)`. Odnotowaliśmy spory postęp.
Kolejny krok to dzielenie `238 : 34`, w wyniku którego otrzymujemy liczbę całkowitą `7`, czyli resztę `0`. Ostatni użyty dzielnik `34` był więc szukanym największym wspólnym dzielnikiem: `NWD(986,748) = 34`.
Obliczmy teraz największy wspólny dzielnik liczb `1309` i `1105`. Próba rozkładu na czynniki może i tu okazać się nieco uciążliwa, posłużymy się zatem zmodyfikowanym algorytmem Euklidesa. Widać „na oko”, że można sobie odpuścić pierwsze dzielenie i zamiast tego odjąć rozpatrywane liczby: `1309 - 1105 = 204`. Zatem `NWD(1309,1105) = NWD(1105,204)`.
Teraz wykonujemy dzielenie: `1105 : 204 = 5.4166666…`, od wyniku odejmujemy całości (`5`) i resztę wymnażamy przez dzielnik: `0.4166666… * 204 = 85` (jeśli kalkulator zwróci liczbę bardzo niewiele różniącą się, wynik zaokrąglamy). Wnioskujemy, że `NWD(1309,1105) = NWD(204,85)`.
Próba kolejnego dzielenia `204 : 85` daje wynik `2.4`. Odejmujemy całości i wykonujemy mnożenie przez dzielnik: `0.4 * 85 = 34`. Wnioskujemy, że `NWD(1309,1105) = NWD(85,34)`.
Czas na kolejne dzielenie: `85 : 34 = 2.5`, odejmujemy `2`, mnożymy część po przecinku przez `34`, otrzymując `0.5 * 34 = 17`. Wnioskujemy, że `NWD(1309,1105) = NWD(34,17)`.
Nawet bez kalkulatora widać, że `17 | 34` (`17` jest dzielnikiem `34`). Zatem `NWD(1309,1105) = 17`.
Rozwiążemy jeszcze jeden przykład: `NWD(10693,2220)`. Próba rozkładu na czynniki zwłaszcza pierwszej z tych liczb jest bardzo uciążliwa (można spróbować!), algorytm Euklidesa będzie więc najlepszym rozwiązaniem.
Wykonujemy więc dzielenie: `10693 : 2220 = 4.8166666…`. Znana procedura doprowadzi nas do otrzymania reszty: `4.8166666… - 4 = 0.8166666…`, `0.8166666… * 2220 = 1813`. Otrzymujemy więc, że `NWD(10693,2220) = NWD(2220,1813)`.
Widać, że mniejsza z liczb nie zmieści się w większej więcej niż raz, stąd odejmujemy: `2220 - 1813 = 407`, co daje nam `NWD(10693,2220) = NWD(1813,407)`.
Możemy znów wrócić do dzielenia z resztą, możemy też czterokrotnie odjąć `407` od `1813`. Pamiętajmy, że jeśli dzielenie z resztą przysparza kłopotów, zawsze możemy wykonać kilkakrotne odejmowanie: `1813 - 4*407 = 185`. Niezależnie od sposobu obliczenia otrzymujemy na tym etapie, że `NWD(10693,2220) = NWD(1813,185)`.
Nawet bez kalkulatora odgadniemy, że `185` mieści się dziewięć razy w `1813`, możemy zatem wykonać działanie `1813 - 9*185 = 148`. Wnioskujemy, że `NWD(10693,2220) = NWD(185,148)`.
I znów ograniczymy się do odjęcia obu liczb. `185 - 148 = 37`, zatem `NWD(10693,2220) = NWD(148,37) = 37`, bo `37 | 148`. Nawet bez kalkulatora można przecież zauważyć, że `148 = 4 * 37`. Szukanym największym wspólnym dzielnikiem jest więc `37`.
8.1. Przez jaką największą liczbę można skrócić ułamki:
| `12/3`, | `8/12`, | `15/6`, | `4/14`, | `11/111`, | `110/100`, |
| `6/40`, | `6/42`, | `1680/2160`, | `336/180`, | `390/715`, | `143/221`. |
Przedstaw je w postaci nieskracalnej.
rozwiązanie