Algorytm Euklidesa

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.

Przykład 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 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, reszty 30
48:30=1, reszty 18
30:18=1, reszty 12
18:12=1, reszty 6
12:6=2, reszty 0

WSTECZ

2020 Karolina Majchrzak