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

  • 5 мин чтения
  • Послушать — 6 мин
  • 12 карточек

Математика, 7 класс · Л. Г. Петерсон, Д. Л. Абраров, Е. В. Чуткова · § 1. Делимость на множестве натуральных чисел

Эта тема о том, как быстро найти наибольший общий делитель больших чисел: он нужен, например, чтобы сокращать дроби. Сначала вспомним определение.

Наибольший общий делитель натуральных чисел a и b — наибольшее из чисел, на которые делятся и a, и b; его обозначают НОД(a; b). Договариваются, что НОД(a; 0) = a: число 0 делится на любое натуральное число.

Искать НОД через разложение на простые множители для больших чисел трудно: нужно делить на многие простые числа. Есть способ проще — алгоритм Евклида. Он основан на теореме:

Если a = bc + r, то НОД(a; b) = НОД(b; r).

Действительно, если d делит a и b, то d делит и r = a - bc; а если d делит b и r, то d делит и a = bc + r. Общие делители у пар (a; b) и (b; r) одни и те же — значит, и наибольший общий.

Алгоритм: делим a на b с остатком, потом делитель — на остаток, потом прежний остаток — на новый, и так далее. Остатки уменьшаются и когда-нибудь станут равны нулю. НОД равен последнему ненулевому остатку.

Пример. НОД(119 597; 52 029):

119 597 = 52 029 · 2 + 15 539

52 029 = 15 539 · 3 + 5412

15 539 = 5412 · 2 + 4715

5412 = 4715 · 1 + 697

4715 = 697 · 6 + 533

697 = 533 · 1 + 164

533 = 164 · 3 + 41

164 = 41 · 4 + 0

Последний ненулевой остаток — 41, значит, НОД(119 597; 52 029) = 41.

Сократить дробь до несократимой — значит разделить числитель и знаменатель на их НОД.

Зачем это

1 / 12

Зачем алгоритм Евклида

Как найти наибольший общий делитель больших чисел: скажем, 119 597 и 52 029? Он нужен, например, чтобы сокращать дроби.

Через разложение на простые множители это трудно: нужно делить на многие простые числа.

Есть способ проще — алгоритм Евклида: только деление с остатком.

Определение

2 / 12

Наибольший общий делитель

Вспомним: НОД натуральных чисел a и b — наибольшее из чисел, на которые делятся и a, и b. Обозначение: НОД(a; b).

НОД(12; 18) = 6.

Договорились: НОД(a; 0) = a — число 0 делится на любое натуральное число.

Правило

3 / 12

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

Чтобы найти НОД(a; b), где a > b:

  1. Делим a на b с остатком.
  2. Делитель делим на остаток, прежний остаток — на новый, и так далее.
  3. Остатки уменьшаются и когда-нибудь станут равны нулю.

НОД равен последнему ненулевому остатку.

Разбор

4 / 12

НОД(252; 198)

Найди НОД(252; 198) алгоритмом Евклида.

  1. Деления

    252 = 198 · 1 + 54

    198 = 54 · 3 + 36

  2. До нуля

    54 = 36 · 1 + 18

    36 = 18 · 2 + 0

  3. Ответ

    Последний ненулевой остаток 18: НОД(252; 198) = 18.

Пример

5 / 12

Большие числа

НОД(119 597; 52 029) — восемь делений с остатком. Остатки:

15 539, 5412, 4715, 697, 533, 164, 41, 0

Последний ненулевой — 41: НОД равен 41.

Частая ошибка

6 / 12

Не частное и не нуль

Последняя строка: 164 = 41 · 4 + 0.

Ошибка — назвать НОД неполным частным 4 или нулём.

НОД — последний ненулевой остаток: 41. Проверка: 119 597 = 41 · 2917, 52 029 = 41 · 1269.

Проверь себя

7 / 12

Чему равен НОД?

НОД — последний ненулевой остаток.

Алгоритм для 48 и 30 закончился строкой 12 = 6 · 2 + 0. НОД(48; 30) =

2612
Ответ и объяснение

48 = 30 · 1 + 18, 30 = 18 · 1 + 12, 18 = 12 · 1 + 6, 12 = 6 · 2 + 0: НОД равен 6.

Правило

8 / 12

Почему алгоритм работает

Почему ответ — последний остаток? Алгоритм основан на теореме Евклида: если a = bc + r, то

НОД(a; b) = НОД(b; r)

54 = 24 · 2 + 6, 24 = 6 · 4 + 0, поэтому

НОД(54; 24) = НОД(24; 6) = НОД(6; 0) = 6.

Свойство

9 / 12

Доказательство теоремы

Докажем теорему. Пусть a = bc + r.

  • Если d делит a и b, то d делит и r = a - bc.
  • Если d делит b и r, то d делит и a = bc + r.

Общие делители пар (a; b) и (b; r) одни и те же — значит, и наибольший общий.

Проверь себя

10 / 12

Какая пара?

a = bc + r: пара (a; b) → пара (b; r).

100 = 36 · 2 + 28. Значит, НОД(100; 36) =

НОД(36; 28)НОД(100; 28)НОД(2; 28)
Ответ и объяснение

Делитель 36 и остаток 28: НОД(100; 36) = НОД(36; 28).

Правило

11 / 12

Сокращаем дробь

Вот где НОД нужен на деле. Сократить дробь до несократимой — значит разделить числитель и знаменатель на их НОД.

НОД(198; 252) = 18:

198/252 = (198 : 18)/(252 : 18) = 11/14

Главное

12 / 12

Главное

  • НОД(a; b) — наибольший общий делитель; НОД(a; 0) = a.
  • Делим с остатком, пока остаток не станет 0; НОД — последний ненулевой остаток.
  • Способ работает, потому что a = bc + r ⇒ НОД(a; b) = НОД(b; r).
  • Сократить дробь — разделить числитель и знаменатель на НОД.

Проверь себя: тест по теме

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

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест