NWD i NWW

Mówimy, że liczba $a$ dzieli liczbę $b$ (piszemy $a \mid b$), gdy $b$ jest wielokrotnością $a$:

Zanim zaczniemy szukać wspólnych dzielników, warto znać cechy podzielności — pozwalają rozpoznać dzielnik bez dzielenia:

• przez 2 — gdy ostatnia cyfra jest parzysta,
• przez 3 — gdy suma cyfr dzieli się przez 3,
• przez 4 — gdy liczba z dwóch ostatnich cyfr dzieli się przez 4,
• przez 5 — gdy ostatnia cyfra to 0 lub 5,
• przez 9 — gdy suma cyfr dzieli się przez 9,
• przez 10 — gdy ostatnia cyfra to 0.

Największy wspólny dzielnik

NWD dwóch liczb to największa liczba, przez którą dzielą się obie:

Najprostsza metoda to wypisanie dzielników obu liczb i wybranie największego wspólnego:

Gdy $\text{NWD}(a, b) = 1$, liczby nie mają wspólnego dzielnika poza jedynką — mówimy, że są względnie pierwsze. Tak jest na przykład dla $8$ i $15$, choć żadna z nich nie jest liczbą pierwszą.

Algorytm Euklidesa

Wypisywanie dzielników staje się niewygodne przy większych liczbach. Szybsza jest zależność znana od ponad dwóch tysięcy lat:

Zastępujemy parę liczb parą „mniejsza liczba i reszta z dzielenia", aż reszta wyniesie zero. Ostatnia niezerowa liczba to szukane NWD.

Najmniejsza wspólna wielokrotność

NWW to najmniejsza dodatnia liczba podzielna przez obie:

Wielokrotności $4$: $4, 8, \mathbf{12}, 16, 20, 24, \ldots$; wielokrotności $6$: $6, \mathbf{12}, 18, 24, \ldots$ — pierwsza wspólna to $12$, czyli $\text{NWW}(4, 6) = 12$.

Nie trzeba jednak niczego wypisywać, bo NWD i NWW są ze sobą związane:

Po co to w praktyce

Oba pojęcia wracają przy ułamkach zwykłych: NWD licznika i mianownika skraca ułamek do postaci nieskracalnej, a NWW mianowników to najmniejszy wspólny mianownik przy dodawaniu. Poza matematyką NWW odpowiada na pytania typu „co ile dni oba autobusy odjadą jednocześnie", a NWD — „jak duże równe kafle pokryją prostokąt bez docinania".

Częste błędy

• Mylenie NWD z NWW — NWD jest nie większy od obu liczb, NWW nie mniejszy; jeśli wynik wypada odwrotnie, to sygnał pomyłki.
• Branie iloczynu liczb jako NWW — $a \cdot b$ jest wspólną wielokrotnością, ale najmniejszą tylko wtedy, gdy liczby są względnie pierwsze.
• Przerwanie algorytmu Euklidesa o krok za późno — NWD to ostatnia niezerowa reszta, a nie zero, na którym kończy się procedura.
• Uznawanie liczb za względnie pierwsze, bo „obie są złożone" — $8$ i $15$ są złożone, a mimo to $\text{NWD}(8, 15) = 1$.