Найти НОД и НОК чисел – онлайн калькулятор

Метод расчета НОД и НОК разложением на простые числа.

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

Содержание

См. также:

Онлайн калькулятор

Результат вычислений

Исходные числа:
120, 3315.
Их наибольший общий делитель:
НОД = 15 (все исходные числа делятся на НОД без остатка).
Наименьшее общее кратное:
НОК = 26520 (НОК делится на все исходные числа без остатка).

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

Подробное решение задачи

Нахождение НОД и НОК с помощью алгоритма Евклида

Условие задачи

Нам заданы следующие натуральные числа:
a₁ = 120, a₂ = 3315.
Найдем их наибольший общий делитель (сокращенно НОД) и наименьшее общее кратное (сокращенно НОК), применяя алгоритм Евклида.

Расчет НОД

Находим НОД чисел a₁ = 120 и a₂ = 3315. Для этого вычисляем остатки от деления больших чисел на меньшие (остатки содержат все общие делители делимого и делителя).
3315 mod 120 = 75 (3315 = 120 * 27 + 75);
120 mod 75 = 45 (120 = 75 * 1 + 45);
75 mod 45 = 30 (75 = 45 * 1 + 30);
45 mod 30 = 15 (45 = 30 * 1 + 15);
30 mod 15 = 0 (30 = 15 * 2 + 0).
Последний ненулевой остаток 15 является наибольшим общим делителем чисел a₁ и a₂.
НОД(a₁, a₂) = НОД(120, 3315) = 15.

Расчет НОК

Находим НОК чисел a₁ = 120 и a₂ = 3315 по формуле:
НОК(a₁, a₂) = a₁ * a₂ / НОД(a₁, a₂).
НОД чисел a₁ и a₂ мы уже нашли.
НОД(a₁, a₂) = НОД(120, 3315) = 15.

Вычисляем НОК.
НОК(a₁, a₂) = a₁ * a₂ / НОД(a₁, a₂) = 120 * 3315 / 15 = 26520.

Ответ

Исходные числа: 120, 3315
имеют наибольший общий делитель и наименьшее общее кратное:
НОД = 15, НОК = 26520.

Вычисление НОД и НОК разложением на простые множители

Разложим исходные числа на простые множители (подробное решение).
120 = 2³·3·5;
3315 = 3·5·13·17.

Перепишем разложения, чтобы в каждом из них присутствовали все встречающиеся простые множители.

120 =	2³·3¹·5¹·13⁰·17⁰
3315 =	2⁰·3¹·5¹·13¹·17¹

Находим минимальные значения степеней простых чисел в разложениях.
Степени множителя 2: min(3, 0) = 0;
степени множителя 3: min(1, 1) = 1;
степени множителя 5: min(1, 1) = 1;
степени множителя 13: min(0, 1) = 0;
степени множителя 17: min(0, 1) = 0.
Возводя множители в минимальные значения, получаем наибольший общий делитель:

НОД = 2⁰·3¹·5¹·13⁰·17⁰ = ·1·3·5·1·1 = 15.

Находим максимальные значения степеней.
Степени множителя 2: max(3, 0) = 3;
степени множителя 3: max(1, 1) = 1;
степени множителя 5: max(1, 1) = 1;
степени множителя 13: max(0, 1) = 1;
степени множителя 17: max(0, 1) = 1.
Возводя множители в максимальные значения, получаем наименьшее общее кратное:

НОК = 2³·3¹·5¹·13¹·17¹ = ·8·3·5·13·17 = 26520.

Ответ

Исходные числа: 120, 3315.
Их наибольший общий делитель:
НОД = 15.
Наименьшее общее кратное:
НОК = 26520.

Разложение натуральных чисел на простые множители

Разложение натурального числа 120 на простые множители

120 = 2*2*2*3*5;
120 = 2³*3*5.

Ход вычислений

120 / 2 = 60;
60 / 2 = 30;
30 / 2 = 15;
15 / 3 = 5;
5 – простое число.

Разложение натурального числа 3315 на простые множители

3315 = 3*5*13*17.

Ход вычислений

3315 / 3 = 1105;
1105 / 5 = 221;
221 / 13 = 17;
17 – простое число.

Описание калькулятора

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

Калькулятор использует длинную арифметику и позволяет работать с большими числами. Однако, если одно из чисел превышает максимально допустимое значение, равное 9007199254740991, то калькулятор выполнит решение задачи только одним способом – методом Евклида.

Справочные данные

Наибольший общий делитель (НОД) чисел: Пусть у нас заданы два или более натуральных числа: a₁, a₂, a₃, ... .
Наибольшим общим делителем заданных чисел (сокращенно НОД) называется наибольшее натуральное число d, на которое делятся без остатка все заданные числа. То есть d – это наибольшее натуральное число, для которого выполняются следующие равенства.
a₁ = m₁·d + 0;
a₂ = m₂·d + 0;
a₃ = m₃·d + 0;
............... ,
где m₁, m₂, m₃, ... – натуральные числа.
Наименьшее общее кратное (НОК) чисел: Пусть у нас заданы два или более натуральных числа: a₁, a₂, a₃, ... .
Наименьшим общим кратным заданных чисел (сокращенно НОК) называется наименьшее натуральное число k, которое делятся без остатка на все заданные числа. То есть k – это наименьшее натуральное число, для которого выполняются следующие равенства.
k = m₁·a₁ + 0;
k = m₂·a₂ + 0;
k = m₃·a₃ + 0;
............... ,
где m₁, m₂, m₃, ... – натуральные числа.
Натуральный ряд: – это последовательность чисел, первое из которой является единицей 1, и каждый последующий элемент получается из предыдущего прибавлением единицы. То есть это ряд, возникающий в процессе счета: 1, 2, 3, 4, ...
Натуральное число: – это число, которое является элементом натурального ряда. То есть это одно из чисел, возникающих в процессе счета: 1, 2, 3, 4, ...
Простое число: – это натуральное число, большее единицы, которое делится без остатка только на единицу и самого себя.
То есть натуральное число p является простым, если для любых m ∈ ℕ и любых n ∈ ℕ, n ≠ 1, n ≠ p выполняется неравенство:
p ≠ m·n + 0.
Другими словами, это неравенство выполняется для всех натуральных m и всех натуральных n, исключая 1 и p.
Разложение числа на простые множители: – это математическая операция, в результате которой исходное натуральное число представляется в виде произведения натуральных чисел, каждое из которых является простым числом.

Автор: Олег Одинцов. Опубликовано: 21-01-2023

См. также: