Największy wspólny dzielnik

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 kilku 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