Największy Wspólny Dzielnik, w skrócie NWD, to największa liczba naturalna, która dzieli dwie lub więcej liczb bez reszty.
Przykład:
Dzielniki liczby 18: 1, 2, 3, 6, 9, 18
Dzielniki liczby 12: 1, 2, 3, 4, 6, 12
Wspólne dzielniki: 1, 2, 3, 6
NWD(18, 12) = 6
Do czego służy NWD?
NWD wykorzystuje się między innymi do:
- skracania ułamków,
- rozwiązywania zadań matematycznych z podzielnością,
- obliczania Najmniejszej Wspólnej Wielokrotności,
- algorytmów kryptograficznych i teorii liczb.
Jak obliczyć NWD?
Najbardziej znaną metodą jest algorytm Euklidesa. Można go realizować przez odejmowanie albo przez resztę z dzielenia modulo.
Przykład wersji z modulo:
NWD(48, 18)
48 mod 18 = 12
18 mod 12 = 6
12 mod 6 = 0
NWD = 6
Związek z NWW
NWD jest powiązany z Najmniejszą Wspólną Wielokrotnością wzorem:
NWW(a, b) = a * b / NWD(a, b)
Dlatego algorytm Euklidesa może pomagać w obliczaniu NWW, ale jego bezpośrednim wynikiem jest zawsze NWD.