Kalkulator NWD i NWW

NWD i NWW online, z pełnym rozwiązaniem

Największy wspólny dzielnik (NWD) i najmniejsza wspólna wielokrotność (NWW) to podstawy arytmetyki: poznaje się je w szkole podstawowej przy ułamkach, a potem wracają w teorii liczb razem z algorytmem Euklidesa i tożsamością Bézouta. Ten kalkulator przyjmuje od 2 do 20 liczb całkowitych i pokazuje drogę do wyniku: kolejne dzielenia, rozkład na czynniki pierwsze, współczynniki Bézouta i ułamek nieskracalny.

Szybkie wyznaczanie NWD i NWW przydaje się przy skracaniu ułamków, sprowadzaniu do wspólnego mianownika, w zadaniach typu „kiedy znów się spotkają?” i przy dzieleniu prostokąta na równe kwadraty. Uczniowie, rodzice sprawdzający prace domowe, nauczyciele przygotowujący rozwiązania i programiści pracujący z cyklami, zębatkami czy kluczami RSA dostają dokładny wynik wraz z pełnym tokiem obliczeń.

1. Wpisz liczby

   W polu „Liczby całkowite (od 2 do 20)” wpisz od 2 do 20 liczb oddzielonych przecinkami, spacjami lub średnikami albo kliknij jeden z przykładów.

2. Odczytaj NWD i NWW

   Dwie karty aktualizują się podczas pisania; przycisk „Kopiuj” kopiuje liczbę bez separatorów do schowka.

3. Sprawdź własności

   Poniżej widać, czy liczby są względnie pierwsze (a przy trzech i więcej liczbach także, czy parami), a dla dwóch liczb również sprawdzenie NWD × NWW = a × b, tożsamość Bézouta i ułamek nieskracalny a/b.

4. Rozwiń objaśnienia

   „Algorytm Euklidesa krok po kroku” pokazuje każde dzielenie a = q × b + r, a „Rozkład na czynniki pierwsze” najmniejsze i największe wykładniki.

Jak obliczyć NWD i NWW: algorytm Euklidesa i czynniki pierwsze

Narzędzie stosuje algorytm Euklidesa: większą liczbę dzieli się z resztą przez mniejszą, a = q × b + r, a potem powtarza to samo dla b i reszty r, ponieważ NWD(a, b) = NWD(b, r). Ostatnia niezerowa reszta to NWD. NWW oblicza się bez rozkładu: NWW(a, b) = a × b ÷ NWD(a, b).

Dla więcej niż dwóch liczb oblicza się łańcuchowo: NWD(a, b, c) = NWD(NWD(a, b), c), i tak samo dla NWW. Panel czynników pierwszych pokazuje drugą szkolną metodę: zapisując a = 2α × 3β × …, NWD bierze każdy wspólny czynnik pierwszy z najmniejszym wykładnikiem, a NWW wszystkie czynniki pierwsze z największym wykładnikiem.

• a i b: dzielna i dzielnik w każdym wierszu (najpierw większa liczba).
• q: iloraz całkowity; r: reszta, zawsze od 0 do b − 1.
• NWD: największa liczba całkowita dzieląca wszystkie liczby; NWW: najmniejsza dodatnia liczba całkowita podzielna przez każdą z nich.
• u i v: współczynniki Bézouta, liczby całkowite (także ujemne), dla których u × a + v × b = NWD(a, b), wyznaczane rozszerzonym algorytmem Euklidesa.
• α, β…: wykładniki w rozkładzie, np. 12 = 2² × 3¹.

Przykłady obliczania NWD i NWW

Do czego służą NWD i NWW?

• Ułamki: skrócić 12/18 do 2/3, dzieląc przez NWD 6, albo dodać 5/12 + 7/18 przy wspólnym mianowniku 36 = NWW(12, 18): 15/36 + 14/36 = 29/36.
• Cykle i rozkłady jazdy: dwa autobusy odjeżdżają razem o 8:00, jeden co 12 minut, drugi co 18; znów razem odjadą o 8:36, po NWW = 36 minutach.
• Cięcie i płytki: aby bez odpadów pokryć płytę 120 cm × 84 cm jak największymi kwadratami, bierze się kwadraty o boku NWD(120, 84) = 12 cm, czyli 10 × 7 = 70 sztuk.
• Zębatki i rytmy: koła o 12 i 18 zębach wracają do położenia początkowego, gdy zazębi się 36 zębów, czyli po 3 obrotach małego i 2 obrotach dużego koła.
• Kryptografia: w RSA wykładnik publiczny e musi być względnie pierwszy z φ(n), a klucz prywatny d jest odwrotnością e modulo φ(n), którą wyznacza się z tożsamości Bézouta. Dla e = 17 i φ(n) = 3120 narzędzie pokazuje (−367) × 17 + 2 × 3120 = 1, skąd d = −367 + 3120 = 2753; rzeczywiście 17 × 2753 = 15 × 3120 + 1.

Częste błędy

• Mylenie NWD z NWW: NWD nigdy nie jest większy od najmniejszej liczby, a NWW nigdy nie jest mniejsza od największej. „NWD” równy 36 dla 12 i 18 jest więc na pewno błędny.
• Mnożenie liczb, by dostać NWW: 12 × 18 = 216, a NWW to 36. Iloczyn dwóch liczb równa się ich NWW tylko wtedy, gdy są one względnie pierwsze (17 × 31 = 527).
• Stosowanie NWD × NWW = iloczyn do trzech liczb: dla 8, 12 i 20 mamy 4 × 120 = 480, a 8 × 12 × 20 = 1920.
• Wpisywanie „12,5” albo „1 071”: przecinek i spacja rozdzielają listę, więc zostaną odczytane dwie liczby (12 i 5 albo 1 i 71). Wpisuj liczby bez odstępów między cyframi: 1071.

Wszystkie obliczenia wykonywane są lokalnie w Twojej przeglądarce, w dokładnej arytmetyce całkowitej (BigInt): żadna liczba nie jest wysyłana na serwer. Ograniczenia: od 2 do 20 niezerowych liczb całkowitych o długości do 15 cyfr; rozkład na czynniki pierwsze pojawia się tylko wtedy, gdy każdy czynnik pierwszy da się szybko znaleźć (dzielenie próbne do 1 000 000, potem test pierwszości).