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

От /

Евклид (III век до н. э.) — великий математик, написавший труд «Начала» — одну из самых важных книг в истории математики.

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

Пример: Чтобы найти НОД(48, 18), Евклид предлагал делить с остатком:

  • 48 : 18 = 2 (ост. 12)
  • 18 : 12 = 1 (ост. 6)
  • 12 : 6 = 2 (ост. 0) → НОД = 6
Алгоритм Евклида

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

Визуализация поиска НОД

Введите числа и нажмите «Запустить» для визуализации алгоритма

Дополнительно

ЕГЭ 2018. Математика. Арифметика и алгебра. Задача 19 (профильный уровень) / Под ред. И. В. Ященко. — М.: МЦНМО. : https://repetitor95.ru/Volfson_19.pdf

Делимость целых чисел в задачах: Сборник задач, — Ханты-Мансийск, Югорский физико-математический лицей, 39 c. : https://ugrafmsh.ru/wp-content/uploads/2015/09/Delimost-tselyih-chisel-v-zadachah.pdf

Источник: https://iro23.ru/wp-content/uploads/2024/04/Вебинар-18.04.2024-Артемова-ОЛ.pdf

Прокрутить вверх