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.