NWD (Największy Wspólny Dzielnik)

Największy wspólny dzielnik (NWD) dwóch lub więcej liczb naturalnych to największa liczba, która dzieli każdą z nich bez reszty. NWD wykorzystuje się m.in. do skracania ułamków do postaci nieskracalnej, rozwiązywania zadań z podziałem przedmiotów na równe grupy oraz w kryptografii i informatyce (np. algorytm Euklidesa, na którym opierają się niektóre metody szyfrowania). Klasyczny algorytm Euklidesa wyznacza NWD dwóch liczb poprzez wielokrotne dzielenie z resztą: dzieli się większą liczbę przez mniejszą, a następnie mniejszą liczbę przez otrzymaną resztę, aż reszta wyniesie zero — wtedy ostatni niezerowy dzielnik jest szukanym NWD.

Przykład: aby znaleźć NWD liczb 48 i 18, dzielimy 48 przez 18, co daje resztę 12 (48 = 2×18 + 12). Następnie dzielimy 18 przez 12, otrzymując resztę 6 (18 = 1×12 + 6). Na koniec dzielimy 12 przez 6, co daje resztę 0 (12 = 2×6 + 0). Ostatnim niezerowym dzielnikiem było 6, więc NWD(48, 18) = 6 — ułamek 48/18 można skrócić do 8/3, dzieląc licznik i mianownik właśnie przez 6.