Algorytm Euklidesa służy do obliczania NWD (największego wspólnego dzielnika) dwóch liczb całkowitych.
Algorytm
Aby obliczyć \(\operatorname{NWD} (a, b)\), wykonujemy kolejno następujące kroki:
- Dzielimy z resztą liczbę \(a\) przez liczbę \(b\)
- jeżeli reszta jest równa \(0\), to \(\operatorname{NWD}(a, b) = b\)
- jeżeli reszta jest różna od \(0\), to przypisujemy liczbie \(a\) wartość liczby \(b\), liczbie \(b\) wartość otrzymanej reszty, a następnie wykonujemy ponownie punkt 1.
Wyznacz największy wspólny dzielnik liczb \(282\) i \(78\).
Zaczynamy od podzielenia liczby \(282\) przez liczbę \(78\) z resztą: \[282 : 78 = 3, \text{ reszty }48\] Otrzymaliśmy resztę różną od zera, zatem teraz podzielimy liczbę \(78\) przez resztę \(48\). Ten schemat będziemy powtarzać do momentu otrzymania reszty równej \(0\). \[ 78 : 48 = 1, \text{ reszty }30\\[6pt] 48 : 30 = 1, \text{ reszty }18\\[6pt] 30 : 18 = 1, \text{ reszty }12\\[6pt] 18 : 12 = 1, \text{ reszty }6\\[6pt] 12 : 6 = 2, \text{ reszty }0 \] Otrzymaliśmy resztę równą zero, zatem szukany NWD będzie równy ostatniej niezerowej reszcie: \[\operatorname{NWD}(282, 78) = 6\]
Jako generator nieskończonej liczby analogicznych przykładów możesz wykorzystać poniższy program.