Наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) нескольких чисел

Наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) нескольких чисел

Положительные целые числа

Рассчитать

Наибольший общий делитель

 

Формула вычисления НОД

 

Наибольшее общее кратное

 

Формула вычисления НОК

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

 Ссылка  Сохранить  Виджет

НОД и НОК нескольких чисел

Вспомним, что НОД, или наибольший общий делитель, это наибольшее натуральное число, на которое без остатка делятся все заданные числа, а НОК, или наименьшее общее кратное, это наименьшее натуральное число, которое делится на каждое из исходных чисел без остатка. В случае двух чисел, НОД можно найти, используя алгоритм Евклида, а НОК можно вычислить поделив произведение двух чисел на НОД.

В случае нескольких чисел можно использовать рекурсивные формулы НОД(a, b, c) = НОД(НОД(a, b), c) и НОК(a, b, c) = НОК(НОК(a, b), c), но есть и более элегантный способ, который и применяется в калькуляторе выше. Чтобы его использовать, необходимо разложить заданные числа на простые множители, т.е. выполнить их факторизацию.

Предположим, что у нас есть разложение чисел a и b на простые множители:

Тогда НОД можно найти как произведение всех имеющихся простых множителей, взятых с минимальной степенью

А НОК - как произведение всех имеющихся простых множителей, взятых с максимальной степенью.

В случае отсутствия множителя в каком либо из чисел, считается что он взят с нулевой степенью.

Способ работает точно также в случае более чем двух чисел. Помимо вычисления собственно НОД и НОК нескольких чисел, калькулятор выше иллюстрирует этот способ. Таблица в калькуляторе показывает разложение заданных чисел на простые множители, а формулы вычисления показывают с какими показателями степени взяты эти множители для нахождения НОД и НОК.