Największy wspólny dzielnik (NWD)

Największy wspólny dzielnik (NWD) dwóch liczb całkowitych to największa liczba, przez którą można podzielić te liczby bez reszty, np. NWD(18, 24) = 6, NWD(12, 21) = 3, NWD(24, 35) = 1.
Największy wspólny dzielnik możemy wyznaczyć również dla większej liczby liczb, np. NWD(30, 85, 90) = 5.
Największy wspólny dzielnik wykorzystujemy podczas skracania ułamków zwykłych.
Jeżeli największym wspólnym dzielnikiem dwóch liczb jest 1, takie liczby nazywamy liczbami względnie pierwszymi. Do takich liczb zaliczamy np. 15 i 32.

W przypadku małych liczb najlepszym sposobem na znalezienie największego wspólnego dzielnika jest wypisanie wszystkich dzielników tych liczb. Aby znaleźć NWD(18, 24), będziemy postępować w następujący sposób:

• Dzielniki liczby 18 to 1, 2, 3, 6, 9, 18.
• Dzielniki liczby 24 to 1, 2, 3, 4, 6, 8, 12, 24.
• Wspólne dzielniki liczb 18 i 24 to 1, 2, 3, 6.
• Największy wspólny dzielnik to 6.

Największy wspólny dzielnik możemy również znaleźć za pomocą rozkładu liczb na czynniki pierwsze. Obydwie liczby zapisujemy w postaci iloczynu liczb pierwszych. NWD to iloczyn wszystkich czynników powtarzających się w obu rozkładach.

• Przykład \mathit{NWD}(18, 24):

• 18 = 2\cdot 3 \cdot 3 = 2\cdot3^2
• 24 = 2 \cdot 2 \cdot 2\cdot 3 = 2^3\cdot 3
• Wspólna część rozkładu na czynniki pierwsze: 2, 3.

• \mathit{NWD}(18, 24) = 2\cdot 3 = 6

• Przykład \mathit{NWD}(540, 315):

• 540 = 2\cdot 2\cdot3\cdot 3\cdot 3\cdot 5 = 2^2\cdot3^3\cdot 5
• 315 = 3\cdot 3 \cdot 5\cdot 7 = 3^2 \cdot 5\cdot 7
• Wspólna część rozkładu na czynniki pierwsze: 3, 3, 5

• \mathit{NSD}(540, 315) = 3\cdot 3\cdot 5 = 3^2\cdot 5 = 45

NWD można obliczać również za pomocą innych metod, do najbardziej znanych należą algorytmy Euklidesa.