Największy wspólny dzielnik (NWD) - Co to jest i jak go obliczyć?

Największy wspólny dzielnik dwóch lub większej ilości liczb to największa liczba dzieląca podane liczby bez reszty. Inaczej można to zdefiniować jako największa liczba, która jest wspólnym dzielnikiem podanych liczb.

Przykłady

Największy wspólny dzielnik dla liczb 12, 8 to 4.

Największy wspólny dzielnik dla liczb 20, 10 to 10.

Największy wspólny dzielnik dla liczb 45, 36 to 9.

Sposób obliczania NWD

W celu obliczenia NWD należy wykorzystać algorytm Euklidesa. Jest to szybka i efektywna metoda. Polega ona na wykonywaniu kolejnych operacji dzielenia z resztą.

Przykład

Obliczamy NWD dla liczb 56 i 42:

1. Dzielimy większą liczbę przez mniejszą:
   56 / 42 = 1 reszta: 14
2. Zamieniamy liczby: 42 i 14
3. Powtarzamy dzielenie:
   42 / 14 = 3 reszta: 0
4. Gdy reszta wynosi 0, ostatnia liczba to NWD:
   NWD(56, 42) = 14