Największy wspólny dzielnik (GCF) to największa liczba, przez którą można podzielić dwie lub więcej liczb. To bez pozostawiania śladów.
Oznacza to, że największy wspólny dzielnik lub GCF to najwyższa liczba, przez którą można podzielić zbiór liczb, dając w wyniku liczbę całkowitą.
Dzielnik można formalnie zdefiniować jako liczbę, która jest zawarta w innej dokładnie n razy.
Należy zauważyć, że liczby, na których obliczany jest GCF, muszą być niezerowe.
Aby to lepiej wyjaśnić, spójrzmy na przykład. Załóżmy, że mamy 35 i 15. W ten sposób obserwujemy, jakie są dzielniki każdego z nich:
- Dzielniki 35 → 35,7,5,1
- Dzielniki 15 → 15,5,3,1
Dlatego największy wspólny dzielnik 35 i 15 wynosi 5.
Warto wspomnieć, że jeśli wspólnymi dzielnikami dwóch liczb są tylko 1 i -1, nazywa się je „pierwszymi dla siebie”.
Metody obliczania największego wspólnego dzielnika
Możemy wyróżnić następujące trzy metody obliczania największego wspólnego dzielnika:
- Rozkład na czynniki pierwsze: Liczby są rozkładane na liczby pierwsze. Następnie, aby obliczyć GCF, bierzemy wspólne liczby podniesione do najniższej potęgi. Załóżmy na przykład, że mamy 216 i 156:
216/2=108
108/2=54
54/2=27
27/3=9
9/3=3
3/3=1
216=(3^3)*(2^3)
156/2=78
78/2=39
39/3=13
13/13=1
156=13*3*(2^2)
Zatem największym wspólnym dzielnikiem między obiema liczbami będzie: (2 2) * 3 = 12
Załóżmy teraz, że mamy trzy elementy: 315, 441 i 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Następnie, po ich rozbiciu, biorąc każdy dzielnik o najniższej potędze, wynik będzie następujący:
GCF = (3 2) * 7 = 63
- Algorytm Euklidesa: Podczas dzielenia do Wejdź botrzymujemy iloraz do i r. Tak więc największy wspólny dzielnik do Tak b jest taki sam jak b Tak r. To, biorąc pod uwagę: a = bc + r. Aby lepiej to zrozumieć, zastosujmy tę metodę do przykładu pokazanego wcześniej z 216 i 156.
216/156 = 1 z resztą 60
teraz dzielimy 156/60 = 2 z resztą 36
Dzielimy ponownie 60/36 = 1 z resztą 24
Jeszcze raz dzielimy 36/24 = 1 z resztą 12
I na koniec dzielimy 24/12 = 2 z resztą 0
Dlatego największym wspólnym dzielnikiem jest 12. Jak widać, musimy dzielić, aż reszta wyniesie 0, a ostatnim dzielnikiem będzie GCF.
- Na podstawie najmniejszej wspólnej wielokrotności: Liczby są mnożone, a wynik dzielony przez ich najmniejszą wspólną wielokrotność (LCM).
Musimy pamiętać, że najmniejsza wspólna wielokrotność (LCM) to najmniejsza liczba spełniająca warunek bycia wielokrotnością wszystkich elementów zbioru liczb.
Oznacza to, że wracając do tego samego przykładu, możemy rozłożyć w następujący sposób:
216 = (3 3) * (2 3) i 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Najmniejsza wspólna wielokrotność to: (3 3) * (2 3) * 13 * 17 * 7 = 334.152
Czyli: NWD = 216 * 156 / 2,808 = 12
Warto wspomnieć, że ta metoda działa tylko dla dwóch liczb.