Приветствую Вас, уважаемые Читатели! Сегодня хочу еще раз окунуться в школьную математику и напомнить Вам о понятиях наибольший общего делителя (НОД) и наименьшего общего кратного (НОК) — простых вещах, настоящем основании теории чисел, которое изучают в 6 классе. Поехали!
Источник: https://w7.pngwing.com/pngs/261/1019/png-transparent-two-children-writing-on-chalkboard-illustration-teacher-mathematics-estudante-math-class-teacher-and-student-child-class-text.png
Наибольший общий делитель
Пусть а и b — некие положительные числа, тогда наибольшее из целых чисел, на которое делится и а и b называется наибольшим общим делителем (НОД). Пример:
Последняя строчка — особенная, ведь из неё следует, что числа 9 и 16 не имеют общих делителей, кроме 1. Такие числа называются взаимно простыми.
- Ввел это понятие Евклид, авторству которого принадлежит теорема о бесконечности простых чисел, которую, например, Г.Г. Харди в своей "Апологии математики" причисляет к красивейшим плодам чистой математики.
Наименьшее общее кратное
Если НОД "подпирает" числа a и b снизу, то наименьшее общее кратное — наоборот, является наименьшим числом, которое делится на a и b без остатка. Пример:
Как видно из примеров, НОД для небольших чисел находить проще, чем НОК. Естественно, что придуманы алгоритмы, которые призваны облегчить нахождение этих величин.
Естественно, НОК И НОД определены и более, чем для двух чисел
Алгоритмы нахождения
Самый простой алгоритм, который фактически реализуется, когда мы подбираем на глазок НОД и НОК, на самом деле основан на основной теореме арифметики, которая утверждает, что каждое натуральное число единственно представимо в виде произведения простых чисел с точностью до порядка сомножителей (подробнее — тут).
Чтобы найти НОК и НОд как раз необходимо это знать каноническое разложение чисел a и b. Давайте разберем на примере чисел 42 и 188, которые уже на "глазок" не раскусить. Итак:
Исходя из этого разложения существует простая формула:
Я выбираю именно такую формулу, сознательно уходя от объяснения на пальцах : если для НОД — это совсем просто (подчеркнуть наибольший общий множитель в обоих разложениях), то для НОК уже надо запоминать некий алгоритм. Лучше знать и понимать одну универсальную формулу.
Там, где простые числа присутствуют в разложении лишь одного числа, пишем нулевую степень. Наименьшее общее кратное вычисляется диаметрально противоположно:
Здесь, описка: вместо НОК написан НОД. Вручную подбор бы затянулся
Как видно, процесс вычисления НОК и НОД требует проведения подготовительного этапа — факторизации, который для больших чисел уже не является тривиальной задачей. Однако, к счастью, для более эффективного вычисления НОД (а, значит, и НОК, ведь их можно выразить друг через друга) еще Евклидом был придуман особый алгоритм. названный его именем. Этот алгоритм по праву считается золотым достоянием математики. О нём поговорим в одной из следующих заметок. Спасибо за внимание!
Читайте также:
- Что такое вероятность: взрослому и ребенку
- Простое объяснение пропорций
- TELEGRAM и Facebook — там я публикую не только интересные статьи, но и математический юмор и многое другое.
