Algorytm Euklidesa jest szybkim sposobem obliczania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych.
Aby obliczyć NWD(a,b), wykonujemy kolejno następujące kroki:
1. Dzielimy z resztą liczbę a przez liczbę b
- jeżeli reszta =0, to NWD(a,b)=b
- jeżeli reszta ?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
Rozwiązanie:
Zaczynamy od podzielenia liczby 282 przez liczbę 78 z resztą:
282:78=3, reszty 48Otrzymaliś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, reszty 30
48:30=1, reszty 18
30:18=1, reszty 12
18:12=1, reszty 6
12:6=2, reszty 0
2020 Karolina Majchrzak