Jesteś tu: SzkołaLiczby i działaniaNajwiększy wspólny dzielnik (NWD)Algorytm Euklidesa

Algorytm Euklidesa

Algorytm Euklidesa jest szybkim sposobem obliczania największego wspólnego dzielnika dwóch (zwłaszcza dużych) 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 \(= 0\), to \(\operatorname{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\).
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.
Program do wyznaczania NWD za pomocą algorytmu Euklidesa Podaj liczby dla których chcesz wyznaczyć NWD:
Liczba 1 =
Liczba 2 =
Sąsiednie tematy
Algorytm Euklidesa (tu jesteś)