Kalkulator NWD — największego wspólnego dzielnika

Kalkulator NWD oblicza największy wspólny dzielnik od dwóch do nawet piętnastu różnych liczb. Czytaj dalej, aby znaleźć odpowiedź na pytanie: „Jaki jest największy wspólny czynnik danych liczb?”, poznaj kilka metod znajdowania NWD, w tym rozkład na czynniki pierwsze lub algorytm Euklidesa. Zdecyduj, która z nich jest twoją ulubioną i sprawdź samodzielnie, że nasz kalkulator NWD może zaoszczędzić czas podczas pracy z dużymi liczbami!

Definicja największego wspólnego dzielnika to największy dzielnik będący liczbą całkowitą, który występuje dla każdej liczby z danego zbioru. Jest on również znany jako największy wspólny czynnik lub największy wspólny mianownik. Jest to istotne zagadnienie w niektórych zastosowaniach matematyki, takich jak upraszczanie wielomianów, gdzie często konieczne jest wyciągnięcie wspólnego czynnika przed nawias. Następnie musimy wiedzieć, jak znaleźć NWD.

Istnieją różne metody, które pomogą ci znaleźć NWD. Niektóre z nich są dziecinnie proste, podczas gdy inne są bardziej złożone. Warto poznać wszystkie z nich, aby móc zdecydować, którą preferujesz:

• wykorzystanie listy wszystkich dzielników;
• rozkład na czynniki pierwsze;
• algorytm Euklidesa;
• algorytm binarny (algorytm Steina); oraz
• korzystanie z wielu właściwości NWD (w tym najmniejszej wspólnej wielokrotności, NWW).

Dobrą wiadomością jest to, że możesz oszacować NWD za pomocą prostych operacji matematycznych bez pierwiastków lub logarytmów! W większości przypadków jest to po prostu odejmowanie, mnożenie lub dzielenie.

Podstawową metodą używaną do oszacowania największego wspólnego dzielnika jest znalezienie wszystkich dzielników podanych liczb. Dzielniki to po prostu liczby, które po pomnożeniu uzyskują pierwotną wartość. Ogólnie rzecz biorąc, mogą one być zarówno dodatnie, jak i ujemne, np. 2 · 3 daje w wyniku to samo co (-2) · (-3), oba iloczyny są równe 6. Z praktycznego punktu widzenia rozważamy tylko wartości dodatnie. Co więcej, w grę wchodzą tylko liczby całkowite. W przeciwnym razie moglibyśmy znaleźć nieskończoną kombinację różnych ułamków będących dzielnikami, co w naszym przypadku jest bezcelowe. Wiedząc o tym, oszacujmy największy wspólny mianownik liczb 72 i 40.

1. Dzielnikami liczby 72 są: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.
2. Dzielnikami liczby 40 są: 1, 2, 4, 5, 8, 10, 20, 40.
3. Wypisz wszystkie wspólne dzielniki: 1, 2, 4, 8.
4. Największym wspólnym dzielnikiem jest 8, najwyższa wartość z powyższych.

Spróbujmy czegoś trudniejszego. Chcemy znaleźć odpowiedź na pytanie: „Jaki jest największy wspólny dzielnik liczb 33 264 i 35 640?” Wszystko, co musimy zrobić, to powtórzyć poprzednie kroki:

1. Dzielnikami liczby 33 264 są: 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 21, 22, 24, 27, 28, 33, 36, 42, 44, 48, 54, 56, 63, 66, 72, 77, 84, 88, 99, 108, 112, 126, 132, 144, 154, 168, 176, 189, 198, 216, 231, 252, 264, 297, 308, 336, 378, 396, 432, 462, 504, 528, 594, 616, 693, 756, 792, 924, 1008, 1188, 1232, 1386, 1512, 1584, 1848, 2079, 2376, 2772, 3024, 3696, 4158, 4752, 5544, 8316, 11 088, 16 632, 33 264.

2. Dzielniki 35 640 to: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 18, 20, 22, 24, 27, 30, 33, 36, 40, 44, 45, 54, 55, 60, 66, 72, 81, 88, 90, 99, 108, 110, 120, 132, 135, 162, 165, 180, 198, 216, 220, 264, 270, 297, 324, 330, 360, 396, 405, 440, 495, 540, 594, 648, 660, 792, 810, 891, 990, 1080, 1188, 1320, 1485, 1620, 1782, 1980, 2376, 2970, 3240, 3564, 3960, 4455, 5940, 7128, 8910, 11 880, 17 820, 35 640.

3. Lista wszystkich wspólnych dzielników: 1, 2, 3, 4, 6, 8, 9, 11, 12, 18, 22, 24, 27, 33, 36, 44, 54, 66, 72, 88, 99, 108, 132, 198, 216, 264, 297, 396, 594, 792, 1188, 2376.

4. Wynik końcowy to: 2376.

Jak widzisz, im większa liczba czynników, tym procedura staje się bardziej czasochłonna, a ryzyko popełnienia błędu wzrasta. Warto wiedzieć, jak działa ta metoda, ale zamiast tego zalecamy skorzystanie z naszego kalkulatora NWD, aby upewnić się, że wynik jest poprawny.

Inna powszechnie stosowana metoda, którą można traktować jako kalkulator największego wspólnego dzielnika, wykorzystuje rozkład na czynniki pierwsze 🇺🇸. Metoda ta jest w pewnym stopniu powiązana z wcześniej wspomnianą. Zamiast wymieniać wszystkie możliwe czynniki, znajdujemy tylko te, które są liczbami pierwszymi. W rezultacie iloczyn wszystkich wspólnych liczb pierwszych jest odpowiedzią na nasz problem, a co ważniejsze, zawsze istnieje dokładnie jeden sposób na faktoryzację dowolnej liczby na liczby pierwsze. Znajdźmy teraz największy wspólny mianownik liczb 72 i 40 przy użyciu rozkładu na czynniki pierwsze:

1. Czynniki pierwsze 72 to: 2, 2, 2, 3, 3.

2. Dzielniki pierwsze liczby 40 to: 2, 2, 2, 5.

3. Innymi słowy, możemy zapisać: 72 = 2 · 2 · 2 · 3 · 3 oraz 40 = 2 · 2· 2 · 5.

4. Wspólna część w obu przypadkach to 2 · 2 · 2 = 8 i jest to jednocześnie największy wspólny dzielnik.

Widzimy, że dla tego prostego przykładu wynik jest zgodny z poprzednią metodą. Sprawdźmy, czy działa ona równie dobrze w bardziej skomplikowanym przypadku. Jaki jest NWD dla 33 264 i 35 640?

1. Dzielnikami pierwszymi liczby 33 264 są: 2, 2, 2, 2, 3, 3, 3, 7, 11.

2. Czynnikami pierwszymi liczby 35 640 są: 2, 2, 2, 3, 3, 3, 3, 5, 11.

3. Możemy użyć notacji wykładniczej do zapisania iloczynów jako: 33 264 = 2⁴ · 3³ · 7 · 11, 35 640 = 2³ · 3⁴ · 5 · 11.

4. Wspólny iloczyn dwóch liczb wynosi 2³ · 3³ · 11. Możemy również zapisać go w bardziej zwięzły i wyrafinowany sposób, z uwzględnieniem silni: (3!)³ × 11. Sprawdź, czy nasz kalkulator największego wspólnego dzielnika daje taki sam wynik, czyli 2376.

Idea, która jest podstawą algorytmu Euklidesa, mówi, że jeśli liczba k jest największym wspólnym dzielnikiem liczb A i B, to k jest również NWD dla różnicy tych liczb A - B. Postępując zgodnie z tą procedurą, w końcu dojdziemy do 0. W rezultacie największy wspólny dzielnik jest ostatnią niezerową liczbą. Przyjrzyjmy się jeszcze raz naszym przykładom — liczbom 40 i 72. Za każdym razem, gdy wykonujemy odejmowanie, porównujemy dwie liczby, porządkując je od największej do najmniejszej:

• NWD z 72 i 40: różnica 72 - 40 równa się 32,
• NWD z 40 i 32: 40 - 32 = 8,
• NWD z 32 i 8: 32 - 8 = 24,
• NWD z 24 i 8: 24 - 8 = 16,
• NWD z 16 i 8: 16 - 8 = 8,
• NWD z 8 i 8: 8 - 8 = 0 STOP!

W ostatnim kroku otrzymujemy 0 z odejmowania. Oznacza to, że znajdujemy nasz największy wspólny dzielnik i jego wartość w przedostatnim wierszu odejmowania: 8.

Co powiesz na trudniejszy przypadek z liczbami 33 264 i 35 640? Spróbujmy go rozwiązać za pomocą algorytmu Euklidesa:

• NWD z 35 640 i 33 264: 35640 - 33 264 = 2376,
• NWD z 33 264 i 2376: 33 264 - 2376 = 30 888,
• NWD z 30 888 i 2376: 30 888 - 2376 = 28 512,
• NWD z 28 512 i 2376: 28 512 - 2376 = 26 136,
• NWD z 26 136 i 2376: 26 136 - 2376 = 23 760,
• NWD z 23 760 i 2376: 23 760 - 2376 = 21 384,
• NWD z 21 384 i 2376: 21 384 - 2376 = 19 008,
• NWD z 19 008 i 2376: 19 008 - 2376 = 16 632,
• NWD z 16 632 i 2376: 16 632 - 2376 = 14 256,
• NWD z 14 256 i 2376: 14 256 - 2376 = 11 880,
• NWD z 11 880 i 2376: 11 880 - 2376 = 9504,
• NWD z 9504 i 2376: 9504 - 2376 = 7128,
• NWD z 7128 i 2376: 7128 - 2376 = 4752,
• NWD z 4752 i 2376: 4752 - 2376 = 2376,
• NWD z 2376 i 2376: 2376 - 2376 = 0 STOP!

Podobnie jak w poprzednim przykładzie, NWD z 33 264 i 35 640 jest ostatnią niezerową różnicą w algorytmie, która wynosi 2376.

Jak widzisz, podstawowa wersja tej metody znajdowania NWD jest bardzo wydajna i prosta, ale ma jedną istotną wadę. Im większa różnica między podanymi liczbami, tym więcej kroków jest potrzebnych do osiągnięcia ostatecznego wyniku. Modulo to skuteczna operacja matematyczna, która rozwiązuje ten problem, ponieważ interesuje nas tylko reszta mniejsza od obu liczb. Powtórzmy algorytm Euklidesa dla naszych przykładów, używając modulo zamiast zwykłego odejmowania:

• NWD z 72 i 40: 72 mod 40 = 32,
• NWD z 40 i 32: 40 mod 32 = 8,
• NWD z 32 i 8: 32 mod 8 = 0 STOP!

Największym wspólnym mianownikiem jest 8. A co z drugim przykładem?

• NWD z 35 640 i 33 264: 35 640 mod 33 264 = 2376,
• NWD z 33 264 i 2376: 33 264 mod 2376 = 0 STOP!

NWD z 35 640 i 33 264 to 2376, i to w zaledwie dwóch krokach zamiast 15. Nieźle, prawda?

Jeśli lubisz operacje arytmetyczne prostsze niż te używane w algorytmie Euklidesa (np. modulo), algorytm binarny (lub algorytm Steina) jest zdecydowanie dla ciebie! Wszystko, czego musisz użyć, to porównywanie, odejmowanie i dzielenie przez 2. Szacując największy wspólny czynnik dwóch liczb, pamiętaj o tych tożsamościach:

1. NWD(A, 0) = A, wykorzystujemy fakt, że zero jest podzielne przez każdą z liczb oraz obserwację z ostatniego kroku algorytmu Euklidesa — gdy jedna z liczb spada do zera, to naszym wynikiem jest ta poprzednia.

2. Jeśli zarówno A, jak i B są parzyste, oznacza to, że NWD(A, B) = 2 · NWD(A/2, B/2) ze względu na fakt, że 2 jest wspólnym czynnikiem.

3. Jeśli tylko jedna z liczb jest parzysta, powiedzmy A, to NWD(A, B) = NWD(A/2, B). Tym razem 2 nie jest wspólnym dzielnikiem, więc możemy kontynuować upraszczanie, aż obie liczby będą nieparzyste.

4. Jeśli A i B są nieparzyste i A > B, to NWD(A, B) = NWD((A-B)/2, B). Tym razem łączymy dwie własności w jednym kroku. Pierwsza z nich wywodzi się z algorytmu Euklidesa, obliczającego największy wspólny dzielnik różnicy obu liczb i mniejszej z nich. Po drugie, dzielenie przez 2 jest możliwe, ponieważ różnica dwóch liczb nieparzystych jest parzysta, a zgodnie z krokiem 3 możemy zmniejszyć liczbę parzystą.

5. Kroki 2-4 są powtarzane aż do osiągnięcia kroku 1 lub jeśli A = B. Wynikiem będzie 2ⁿ · A, gdzie n to liczba czynników 2 znalezionych w drugim kroku.

Jak zwykle, przećwiczmy algorytm z naszymi zestawami liczb. Zaczynamy od 40 i 72:

• Obie są parzyste, więc NWD(72, 40) = 2 · NWD(36, 20) = 2² · NWD(18, 10) = 2³ · NWD(9, 5) = …;

• Pozostałe liczby są nieparzyste, więc … = 2³ · NWD((9-5)/2, 5) = 2³ · NWD(2, 5);

• 2 jest parzyste, więc możemy je zredukować: ... = 2³ · NWD(1, 5);

• 1 i 5 są nieparzyste, więc: … = 2³ · NWD((5-1)/2, 1) = 2³ · NWD(2, 1); oraz

• Usuń 2 z liczby parzystej: … = 2³ · NWD(1, 1) = 2³ = 8.

Właściwie mogliśmy zatrzymać się na trzecim kroku, ponieważ NWD z 1 i dowolnej liczby wynosi 1.
No dobrze, a jak znaleźć największy wspólny czynnik liczb 33 264 i 35 640 metodą binarną?

• dwie liczby parzyste: NWD(35 640, 33 264) = 2 · NWD(17 820, 16 632) = 2² · NWD(8910, 8316) = 2³ · NWD(4455, 4158) = …;

• jedna parzysta, jedna nieparzysta: … = 2³ · NWD(4455, 2079);

• dwie nieparzyste: … = 2³· NWD((4455-2079)/2, 2079) = 2³ · NWD(1188, 2079);

• jedna parzysta, jedna nieparzysta: … = 2³ · NWD(594, 2079) = 2³ · NWD(297, 2079);

• dwie nieparzyste: … = 2³ · NWD((2079-297)/2, 297) = 2³ · NWD(891, 297);

• dwie nieparzyste: … = 2³ · NWD((891-297)/2, 297) = 2³ · NWD(297, 297) = 2³ · 297 = 2376.

Wiemy, że liczby pierwsze to takie, które mają tylko 2 dodatnie i całkowite czynniki: 1 i samą siebie. Pytanie brzmi więc, czym są liczby względnie pierwsze? Możemy je zdefiniować jako liczby, które nie mają wspólnych czynników. Dokładniej, 1 jest ich jedynym wspólnym czynnikiem, ale ponieważ pomijamy 1 w rozkładzie na liczby pierwsze, można powiedzieć, że nie mają one wspólnych dzielników. Innymi słowy, możemy napisać, że liczby A i B są liczbami względnie pierwszymi, jeśli NWD(A,B) = 1. Nie oznacza to, że któraś z nich jest liczbą pierwszą, a jedynie, że lista ich wspólnych dzielników jest pusta. Przykładami par liczb względnie pierwszych są: 5 i 7, 35 i 48, 23 156 i 44 613.

Ciekawostka: możliwe jest obliczenie prawdopodobieństwa, że dwie losowo wybrane liczby są liczbami względnie pierwszymi. Chociaż jest to dość skomplikowane, ogólny wynik wynosi około 61%. Czyż to nie zaskakujące? Po prostu przetestuj to samodzielnie — wyobraź sobie dwie losowe liczby (powiedzmy, że co najmniej 5-cyfrowe), użyj naszego kalkulatora największego wspólnego dzielnika i sprawdź, czy wynik wynosi 1, czy nie. Powtórz grę wiele razy i oszacuj, jaki jest procent znalezionych liczb względnie pierwszych.

Teraz gdy znamy już wiele metod znajdowania największego wspólnego dzielnika dwóch liczb, możesz zapytać: „jak znaleźć największy wspólny czynnik trzech (lub więcej) liczb?”. Okazuje się, że nie jest to tak trudne, jak mogłoby się wydawać na pierwszy rzut oka. Cóż, wypisanie wszystkich czynników dla każdej liczby jest zdecydowanie najbardziej oczywistą metodą, ponieważ możemy po prostu znaleźć największy dzielnik wśród nich. Możesz jednak szybko zdać sobie sprawę, że staje się to coraz bardziej czasochłonne wraz ze wzrostem liczby wartości.

Metoda rozkładu na czynniki pierwsze ma podobną wadę, ale ponieważ możemy pogrupować wszystkie liczby pierwsze, na przykład w kolejności rosnącej, to możemy wprowadzić sposób na uzyskanie wyniku nieco szybciej niż poprzednio.

Z drugiej strony, jeśli wolisz używać algorytmu binarnego lub Euklidesa do oszacowania NWD wielu liczb, możesz również użyć twierdzenia, które mówi, że:

NWD(a, b, c) = NWD(NWD(a, b), c) = NWD(NWD(a, c), b) = NWD(NWD(b, c), a).

Oznacza to, że możemy obliczyć NWD dowolnych dwóch liczb, a następnie rozpocząć algorytm ponownie, używając wyniku i trzeciej liczby i kontynuować, dopóki pozostaną jakieś liczby różne od jedności. Nie ma znaczenia, które dwie liczby wybierzemy jako pierwsze.

Innym pojęciem ściśle związanym z NWD jest najmniejsza wspólna wielokrotność, NWW. Aby znaleźć najmniejszą wspólną wielokrotność, używamy tego samego procesu, którego używaliśmy do znalezienia NWD. Po rozłożeniu liczb na czynniki pierwsze szukamy najmniejszej potęgi każdego czynnika, w przeciwieństwie do największej potęgi. Następnie mnożymy najwyższe potęgi, a wynikiem jest najmniejsza wspólna wielokrotność lub NWW. Możesz to zrobić ręcznie lub za pomocą kalkulatora NWW 🇺🇸.

Największy wspólny dzielnik można oszacować za pomocą NWW. Należy skorzystać z poniższego wyrażenia:

NWD(a, b) = |a · b| / NWW(a, b)

Przydatne może być znalezienie najpierw najmniejszej wspólnej wielokrotności ze względu na złożoność i czasochłonność. Oczywiście można to równanie wykorzystać do obliczania wartości w obie strony, więc warto wiedzieć, jak znaleźć zarówno NWD jak i NWW.

Przedstawiliśmy już kilka właściwości największego wspólnego mianownika. W tym rozdziale wymienimy najważniejsze z nich:

• Jeśli stosunek dwóch liczb a i b (a > b) jest liczbą całkowitą, to NWD(a, b) = b.

• NWD(a, 0) = a, używane w algorytmie Euklidesa.

• NWD(a, 1) = 1.

• Jeśli a i b nie mają wspólnych czynników (są liczbami względnie pierwszymi), to NWD(a, b) = 1.

• Wszystkie wspólne czynniki a i b są również dzielnikami NWD(a, b).

• Jeśli b · c / a jest liczbą całkowitą i NWD(a, b) = d, to a · c / d również jest liczbą całkowitą.

• Dla dowolnej liczby całkowitej k: NWD(k·a, k·b) = k · NWD(a, b), używane w algorytmie binarnym.

• Dla dowolnej dodatniej liczby całkowitej k: NWD(a/k, b/k) = NWD(a, b) / k.

• NWD(a, b) · NWW(a, b) = |a·b|.

• NWD(a, NWW(b, c)) = NWW(NWD(a, b), NWD(a, c)).

• NWW(a, NWD(b, c)) = NWD(NWW(a, b), NWW(a, c)).

Nie, NWD z 14 i 42 to nie 2. NWD liczb 14 i 42 wynosi 14 i aby go znaleźć, rozłóż obie liczby na czynniki:

• dzielniki liczby 14 to 1, 2, 7 i 14,
• dzielniki liczby 42 to 1, 2, 3, 6, 7, 14, 21 i 42.

Jak widzisz, największą wspólną liczbą na obu listach jest 14 i jest to właśnie NWD.

NWD z 8 i 12 wynosi 4. Aby uzyskać tę odpowiedź:

1. Wypisz wszystkie czynniki dla obu liczb:

   • dzielniki liczby 8 to 1, 2, 4 i 8,
   • dzielniki liczby 12 to 1, 2, 3, 4, 6 i 12.

2. Wymień wszystkie wspólne czynniki: 1, 2, 4.

3. Największym wspólnym dzielnikiem jest największy z nich, czyli 4.

NWD z 24 i 36 wynosi 12. Możemy uzyskać tę odpowiedź, stosując algorytm Euklidesa:

1. Posortuj liczby rosnąco:

   24, 36

2. Wykonaj operację modulo, przyjmując największą liczbę jako dzielną, a najmniejszą jako dzielnik:

   36 mod 24 = 12

3. Weź dzielną i resztę i posortuj je w porządku rosnącym:

   12, 24

4. Ponownie wykonaj operację modulo w ten sam sposób:

   24 mod 12 = 0

5. Została tylko jedna liczba (dzielnik, 12), więc 12 jest największym wspólnym dzielnikiem.

NWD liczb 30 i 54 wynosi 6. Możemy użyć rozkładu na czynniki pierwsze, aby uzyskać odpowiedź:

1. Zapisz wszystkie liczby jako iloczyn ich czynników pierwszych:

   • 30 = 2 · 3 · 5
   • 54 = 2 · 3 · 3 · 3

2. Wymień wszystkie wspólne czynniki pierwsze: 2, 3.

3. Znajdź iloczyn wszystkich wspólnych czynników pierwszych: 2 · 3 = 6.

4. Największy wspólny czynnik jest wynikiem poprzedniego kroku. Dla 30 i 54 jest to: 6.