Алгоритм Евклида для НОД. НОД Евклида

Нахождение наибольшего общего делителя двух целых чисел.

Пусть даны целые числа:

A и B
A > B

Алгоритм Евклида по шагам.

1. Если разделить A на B, получим частное k₀ и, возможно, остаток r₁:

A : B = k₀
остаток r₁

Это можно записать так:

A = B * k₀ + r₁

2. Далее, если разделить B на остаток r₁, получим частное k₁ и, возможно, остаток r₂:

B : r₁ = r₁ * k₁
остаток r₂

Это можно записать так:

B = r₁ * k₁ + r₂

3. Далее, если разделить r₁ на остаток r₂, получим частное k₂ и, возможно, остаток r₃:

r₁ : r₂ = r₂ * k₂
остаток r₃

Это можно записать так:

r₁ = r₂ * k₂ + r₃

4. Продолжая таким образом, в какой-то момент получим остаток, равный нулю:

r_{k — 1} : r_k = r_k * k_k
остаток 0

Это можно записать так:

r_{k — 1} = r_k * k_k + 0

Число r_k и будет наибольшим общим делителем целых чисел A и B

НОД(A, B) = r_k

Запишем алгоритм Евклида кратко:

1. A = B * k₀ + r₁
2. B = r₁ * k₁ + r₂
3. r₁ = r₂ * k₂ + r₃
…
k. r_{k — 1} = r_k * k_k + 0

Когда получаем ноль в остатке, поиск наибольшего общего делителя прекращаем ибо НОД уже найден и им является число r_k.

Ответ:

НОД(A, B) = r_k