Jak obliczyć największy wspólny dzielnik dwóch liczb?

Największy wspólny dzielnik (NWD) to największa liczba naturalna, przez którą można podzielić dwie liczby bez reszty. Dla małych liczb najczytelniejszy jest rozkład na czynniki pierwsze, a przy większych liczbach szybciej działa algorytm Euklidesa.

Czym jest NWD?

Dzielnik liczby to liczba, przez którą można ją podzielić bez reszty. Jeśli ta sama liczba dzieli dwie liczby, nazywamy ją ich wspólnym dzielnikiem. Największy z takich dzielników to właśnie NWD.

Przykład: wspólne dzielniki liczb 12 i 18 to 1, 2, 3 oraz 6, dlatego NWD(12, 18) = 6. NWD wykorzystuje się między innymi do skracania ułamków. Ułamek 850/6625 można skrócić przez 25, ponieważ NWD(850, 6625) = 25. Otrzymujemy wtedy 34/265.

Nie należy mylić NWD z NWW, czyli najmniejszą wspólną wielokrotnością. NWD wskazuje największy wspólny dzielnik, a NWW – najmniejszą liczbę będącą wielokrotnością obu liczb.

Metoda rozkładu na czynniki pierwsze

Ta metoda dobrze sprawdza się przy mniejszych liczbach i jest często stosowana w zadaniach szkolnych. Najpierw rozkładasz obie liczby na czynniki pierwsze, a następnie wybierasz czynniki występujące w obu rozkładach. Każdy wspólny czynnik uwzględniasz tyle razy, ile występuje w krótszym rozkładzie.

Procedura wygląda następująco:

• Rozłóż pierwszą liczbę na czynniki pierwsze.
• Rozłóż drugą liczbę na czynniki pierwsze.
• Wybierz wspólne czynniki występujące w obu rozkładach.
• Pomnóż wspólne czynniki, aby otrzymać NWD.

Obliczmy NWD liczb 36 i 48:

36 = 2 · 2 · 3 · 3

48 = 2 · 2 · 2 · 2 · 3

W obu rozkładach występują dwa czynniki 2 oraz jeden czynnik 3. Zatem:

NWD(36, 48) = 2 · 2 · 3 = 12

Metoda jest intuicyjna, ale przy dużych liczbach samo rozkładanie na czynniki pierwsze może być czasochłonne. Wtedy lepiej zastosować algorytm Euklidesa.

Algorytm Euklidesa – szybkie obliczanie NWD

Algorytm Euklidesa wykorzystuje dzielenie z resztą, czyli operację modulo. Opiera się na zasadzie, że NWD dwóch liczb nie zmienia się, gdy większą liczbę zastąpimy resztą z dzielenia jej przez mniejszą.

Aby obliczyć NWD liczb 999 i 3108, wykonaj kolejne dzielenia:

1. 3108 = 3 · 999 + 111, więc 3108 mod 999 = 111.
2. 999 = 9 · 111 + 0, więc 999 mod 111 = 0.
3. Gdy reszta wynosi 0, ostatnia niezerowa reszta, czyli 111, jest wynikiem.

Otrzymujemy NWD(999, 3108) = 111. Rzeczywiście, 999 : 111 = 9, a 3108 : 111 = 28.

W zapisie skróconym algorytm można przedstawić tak:

Dopóki druga liczba nie jest równa 0:
reszta = pierwsza liczba mod druga liczba
pierwsza liczba = druga liczba
druga liczba = reszta
Wynikiem jest pierwsza liczba.

Algorytm działa także wtedy, gdy początkowo podasz liczby w odwrotnej kolejności. Jeśli NWD dwóch liczb wynosi 1, liczby te nazywamy względnie pierwszymi.

Metoda szkolna czy algorytm Euklidesa?

Najważniejsza wskazówka

Przy małych liczbach możesz wybrać rozkład na czynniki pierwsze, ponieważ łatwo prześledzić wszystkie etapy. Gdy liczby są duże albo trzeba wykonać wiele obliczeń, wybierz algorytm Euklidesa. Pamiętaj, że NWD oznacza największy, a nie najmniejszy wspólny dzielnik.