Наибольший общий делитель и наименьшее общее кратное с шагами алгоритма Евклида.
Ваш пример
Разбор примера
НОД = 6; НОК = 72
Работаем с модулями: 18 и 24.
18 = 24 × 0 + 18.
24 = 18 × 1 + 6.
18 = 6 × 3 + 0.
Последний ненулевой остаток или исходное ненулевое число: НОД = 6.
НОК = |(18 / 6) × (24)| = 72.
НОД
6
НОК
72
Разобраться в теме
НОД отвечает на вопрос о наибольшем общем размере деления без остатка. НОК — о первом положительном числе, в котором укладываются оба исходных периода или размера.
Выбор между ними определяется вопросом задачи. Поиск одинаковых самых длинных кусочков и поиск первого совместного повторения требуют разных результатов даже для одной пары чисел.
Делитель и кратное направлены в разные стороны
Общий делитель делит каждое исходное число. Общие кратные, наоборот, делятся на оба исходных числа.
Для положительных a и b НОД не превосходит меньшего числа, а НОК не меньше большего. Эти оценки помогают заметить перепутанный ответ.
Почему работает остаток
Если a = qb + r, любой общий делитель a и b делит и r = a − qb. Обратно, общий делитель b и r делит a.
Поэтому заменяем пару (a,b) парой (b,r), пока остаток не станет нулём. Последний ненулевой остаток — НОД.
Связь двух результатов
Для ненулевых целых НОК = |a/НОД × b|. Деление до умножения позволяет не раздувать промежуточное произведение.
Проверьте, что НОД делит оба числа, НОК кратен обоим и НОД × НОК = |ab|. Знаки исходных чисел для этих неотрицательных результатов несущественны.