Основное содержание
Информатика
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)
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.