Основное содержание

Course: Информатика > Модуль 2

Урок 5: Модульная арифметика

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

Как вы помните, наибольший общий делитель (НОД) для двух целых чисел A и B — это наибольшее натуральное число, на которое делятся и A, и B

Алгоритм Евклида — это метод быстрого нахождения НОД для двух целых чисел.

Алгоритм

Алгоритм Евклида для нахождения НОД(A, B) выглядит следующим образом:

Если A = 0, тогда НОД(A, B) = B, поскольку НОД(0, B) = B, и алгоритм останавливается.
Если B = 0, тогда НОД(A, B) = A, поскольку GCD(A, 0) = A, и алгоритм останавливается.
Делим A на B с остатком (A = B⋅Q + R)
Находим НОД(B, R) при помощи алгоритма Евклида, поскольку НОД(A ,B) = НОД(B, R)

Пример:

Найдите НОД из 270 и 192

A=270, B=192
A ≠0
B ≠0
Делим столбиком A на B, получается 270/192 = 1 с остатком 78. Можем записать результат в виде: 270 = 192 * 1 +78
Ищем НОД(192, 78), поскольку НОД(270, 192) = НОД(192, 78)

A=192, B=78

A ≠0
B ≠0
Делим столбиком A на B, получается 192/78 = 2 с остатком 36. Можем записать результат в виде:
192 = 78 * 2 + 36
Ищем НОД(78, 36), поскольку НОД(192, 78) = НОД(78, 36)

A=78, B=36

A ≠0
B ≠0
Делим столбиком A на B, получается 78/36 = 2 с остатком 0. Можем записать результат в виде:
78 = 36 * 2 + 6
Ищем НОД(36,6), поскольку НОД(78,36) = НОД(36,6)

A=36, B=6

A ≠0
B ≠0
Делим столбиком A на B, получается 36/6 = 6 с остатком 0. Можем записать результат в виде:
36 = 6 * 6 + 0
Ищем НОД(6,0), поскольку НОД(36,6) = НОД(6,0)

A=6, B=0

A ≠0
B =0, НОД(6,0)=6

Итак, мы показали:

НОД(270,192) = НОД(192,78) = НОД(78,36) = НОД(36,6) = НОД(6,0) = 6

НОД(270,192) = 6

Принцип работы алгоритма Евклида

Алгоритм Евклида основан на следующих свойствах:

НОД(A,0) = A
НОД(0,B) = B
Если A = B⋅Q + R и B≠0, то НОД(A, B) = НОД(B, R), где Q — целое число, а R — целое число от 0 до B-1

Первые два свойства позволяют нам найти НОД, когда одно из чисел равно 0. С помощью третьего свойства мы можем взять большие числа и уменьшить их для упрощения задачи.

Алгоритм Евклида позволяет при помощи третьего свойства очень быстро сводить исходную задачу к всё более и более простым, пока она не решится совсем легко при помощи первых двух свойств.

Мы можем понять принцип действия алгоритма, доказав эти три свойства.

Мы можем доказать, что НОД(A, 0) = A, следующим образом:

Наибольшее число, на которое A делится без остатка, — это A.
Число 0 делится на все целые числа, поскольку для любого целого C верно выражение C ⋅ 0 = 0. Следовательно, 0 делится на A без остатка.
Следовательно, наибольший общий делитель чисел A и 0 — это A.

Аналогично доказывается, что НОД(0, B)=B (принцип доказательтва тот же, только A заменяем на B).

Чтобы доказать, что НОД(A, B) = НОД(B, R), мы должны сначала доказать, что НОД(A, B) = НОД(B, A-B).

Возьмём три целых числа A, B и C, такие что A-B = C.

Доказательство того, что НОД(A, B) является делителем числа C

По определению, A делится на НОД(A, B) без остатка. Следовательно, A кратно НОД(A, B), то есть существует такое целое X, что X⋅НОД(A, B)=A.

По определению, B делится на НОД(A, B) без остатка. Следовательно, B кратно НОД(A, B), то есть существует такое целое Y, что Y⋅НОД(A, B)=B.

A-B=C даёт нам:

X⋅НОД(A,B) - Y⋅НОД(A,B) = C
(X - Y)⋅НОД(A,B) = C

То есть, как видим, НОД(А, B) является делителем числа C.

Данное доказательство проиллюстрировано на левой части схемы:

Доказательство того, что НОД(B, C) является делителем числа A

По определению, B делится на НОД(B, C) без остатка. Следовательно, B кратно НОД(B, C), то есть существует такое целое M, что M⋅НОД(B, C)=B.

По определению, C делится на НОД(B, C) без остатка. Следовательно, C кратно НОД(B, C), то есть существует такое целое N, что N⋅НОД(B, C)=N.

A-B=C даёт нам:

B+C=A
M⋅НОД(B, C) + N⋅НОД(B, C) = A
(M + N)⋅НОД(B, C) = A

То есть, как видим, НОД(B, C) является делителем числа A.

Данное доказательство можно проиллюстрировать следующей схемой

Доказательство того, что НОД(A, B) = НОД(A, A-B)

По определению, число B делится на НОД(A, B) без остатка.
Мы доказали, что НОД(A, B) является делителем C.
Поскольку НОД(A, B) является делителем и числа B, и числа C, значит, это общий делитель чисел B и C.

НОД(A, B) должен быть меньше или равен НОД(B, C), поскольку НОД(B, C) — «наибольший» общий делитель чисел B и C.

По определению, число B делится на НОД(B, C) без остатка.
Мы доказали, что НОД(B, C) является делителем A.
Поскольку НОД(B, C) является делителем и числа A, и числа B, значит, это общий делитель чисел A и B .

НОД(B, C) должен быть меньше или равен НОД(A, B), поскольку НОД(A, B) — «наибольший» общий делитель чисел A и B.

Значит, раз НОД(A, B) ≤ НОД(B, C) и НОД(B, C) ≤ НОД(A, B), тогда мы можем сделать вывод:

НОД(A, B)=НОД(B, C)

Что эквивалентно:

НОД(A, B)=НОД(B, A-B)

Данное доказательство проиллюстрировано на правой части схемы:

Доказательство того, что НОД(A, B) = НОД(B, R)

Мы доказали, что НОД(A, B) = НОД(B, A-B)

Порядок чисел не имеет значения, то есть, мы можем сказать, что НОД(A, B) = НОД(A-B, B)

Мы можем многократно применить свойство НОД(A, B) = НОД(A-B, B), тогда получится:

НОД(A, B)=НОД(A-B, B)=НОД(A-2B, B)=НОД(A-3B, B)=...=НОД(A-Q⋅B, B)

Однако A= B⋅Q + R, поэтому A-Q⋅B=R

Из этого следует, что НОД(A, B)=НОД(R, B)

Порядок чисел не имеет значения, следовательно:

НОД(A, B)=НОД(B, R)

Хотите присоединиться к обсуждению?

Войти

Сортировать по:

Пока нет ни одной записи.

Знаете английский? Нажмите здесь, чтобы увидеть обсуждение, которое происходит на английской версии сайта.