НОД и НОК двух целых чисел

Наибольший общий делитель и наименьшее общее кратное с шагами алгоритма Евклида.

Ваш пример

Десятичные числа можно вводить через запятую.

Разбор примера

НОД = 6; НОК = 72

  1. Работаем с модулями: 18 и 24.
  2. 18 = 24 × 0 + 18.
  3. 24 = 18 × 1 + 6.
  4. 18 = 6 × 3 + 0.
  5. Последний ненулевой остаток или исходное ненулевое число: НОД = 6.
  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|. Знаки исходных чисел для этих неотрицательных результатов несущественны.

Примеры с разбором

Одна пара — два вопроса

Найти НОД и НОК чисел 84 и 126.

  1. 126 = 84 + 42.
  2. 84 = 2 × 42, поэтому НОД = 42.
  3. НОК = (84/42) × 126 = 252.

Ответ: НОД = 42; НОК = 252.

Проверка: 84/42 = 2, 126/42 = 3; 252/84 = 3, 252/126 = 2. Произведения 42 × 252 и 84 × 126 равны 10584.

Где можно ошибиться

НОК как простое произведение
ab — общее кратное, но при общем делителе больше 1 оно не наименьшее.
Выбор по знакомому слову
«Поровну без остатка» и «одновременно повторится» описывают разные задачи.
Пара нулей
Для 0 и 0 нет наибольшего положительного общего делителя; эта пара отклоняется.

Проверьте понимание

Сигналы повторяются каждые 14 и 21 минуту и сейчас совпали. Когда следующее совпадение?

Вопросы по теме

Что будет с одним нулём?

Для пары 0,b при b ≠ 0 НОД равен |b|. В этом инструменте НОК с нулём принят равным 0; правило о положительном кратном относится к ненулевым числам.

Почему для взаимно простых чисел НОК равен произведению?

У них НОД = 1, поэтому формула |ab|/НОД превращается в |ab|.

Можно ли найти НОД только по разложению?

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

Делимость, простые числа, НОД и НОК: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.