Odpowiedź + Wyjaśnienie:
Algorytm Euklidesa służy do znajdowania NWD (Największego Wspólnego Dzielnika) dwóch liczb.
Mamy dwie wersje algorytmu Euklidesa.
Zawsze odejmujemy mniejszą liczbę od większej i zastępujemy liczbę większą wynikiem odejmowania.
Proces wykonujemy do momentu, aż otrzymamy różnicę równą 0. Wówczas NWD danych liczb, to wartość równa ostatniej niezerowej różnicy.
a = 56, b = 42
a > b
a - b = 56 - 42 = 14
a = 14
b > a
b - a = 42 - 14 = 28
b = 28
b > a
b - a = 28 - 14 = 14
a = b = 14
Zawsze dzielimy większą liczbę przez mniejszą i zastępujemy większą liczbę resztą z dzielenia.
Proces wykonujemy, aż reszta z dzielenia wyniesie 0. Wówczas NWD danych liczb jest ostatnią niezerową resztą z dzielenia.
a = 56, b = 42
a > b
a mod b = 56 mod 42 = 14
a = 14
b > a
b mod a = 42 mod 14 = 0
