Что это
Наибольший общий делитель — самое большое число, на которое делятся оба числа, а наименьшее общее кратное — самое маленькое число, которое делится на оба. Представь, что надо выложить прямоугольный пол одинаковыми квадратными плитками без обрезков: сторона самой большой такой плитки и есть наибольший общий делитель сторон.
Зачем это нужно
Алгоритм Евклида — один из старейших алгоритмов, который до сих пор работает в каждом защищённом соединении: на нём держится криптография, которая охраняет банковские переводы и сообщения в мессенджерах. Наименьшее общее кратное помогает согласовать периодические процессы — расписания транспорта, такты в электронике, циклы работы роботов на конвейере. ИИ напишет такой код в одну строку, но понять, почему алгоритм быстр и правилен, и выбрать его для своей задачи может человек, знающий математику. Программисты, криптографы и инженеры будут ценить это понимание и через десять лет.
Как это работает
Евклид заметил, что общий делитель двух чисел делит и остаток от деления большего на меньшее. Поэтому пару чисел заменяют на меньшее число и остаток, и повторяют, пока остаток не станет нулём; последний ненулевой остаток — это наибольший общий делитель. Геометрически это как отрезать от прямоугольника самые большие квадраты, пока остаток не замостится квадратами без щели. Шагов мало даже для огромных чисел, потому что за каждые два шага остаток уменьшается хотя бы вдвое.
Немного истории
Этот алгоритм описан в «Началах» Евклида — древнегреческом труде, написанном примерно двадцать три века назад в Александрии. Евклид излагал его геометрически, как поиск общей меры двух отрезков. «Начала» стали одной из самых издаваемых книг в истории, а сам алгоритм считают одним из древнейших, которые используются до сих пор.
Формула: алгоритм Евклида
Главное правило: наибольший общий делитель а и бэ равен наибольшему общему делителю бэ и остатка от деления а на бэ. Почему? Число, которое делит и а, и бэ, делит и разницу между а и несколькими бэ, а это и есть остаток. Здесь а и бэ — натуральные числа, а остаток обозначают словом мод. Пару заменяют снова и снова, пока остаток не станет нулём — тогда ответом будет последнее ненулевое число. Чем больше разница в размерах чисел, тем сильнее уменьшается пара за один шаг.
НОД(a, b) = НОД(b, a mod b)a, b — натуральные числа, —
a mod b — остаток от деления a на b, —
Формула: НОК через НОД
Наименьшее общее кратное находят так: оно равно а умножить на бэ, делённому на наибольший общий делитель а и бэ. Произведение а на бэ точно делится на оба числа, но в нём общая часть посчитана дважды, поэтому её убирают делением на общий делитель. Здесь а и бэ — натуральные числа. Например, если два автобуса уходят вместе и ходят с разными интервалами, по этой формуле узнают, через сколько минут они снова уйдут одновременно. Чем больше общий делитель, тем меньше общее кратное по сравнению с произведением.
НОК(a, b) = a · b / НОД(a, b)a, b — натуральные числа, —
НОД(a, b) — наибольший общий делитель, —
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. Сейчас перед тобой режим наибольшего общего делителя: прямоугольник сорок восемь на восемнадцать. Выбирай, сколько самых больших квадратов отрезать за один шаг, — остаток должен получиться меньше стороны квадрата, — и смотри, как прямоугольник становится всё меньше. Когда остаток замостится квадратами без щели, сторона этих квадратов и будет ответом. Потом на линии времени найди наименьшее общее кратное двенадцати и восемнадцати — можно выписать кратные каждого числа или воспользоваться формулой через общий делитель. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.