Методы решения физико-математических задач

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

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

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

Введите натуральные числа   ?

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

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

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

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

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

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

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

Расчет НОД

Находим НОД чисел a1 = 120 и a2 = 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 является наибольшим общим делителем чисел a1 и a2.
НОД(a1, a2) = НОД(120, 3315) = 15.

Расчет НОК

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

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

Ответ

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

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

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

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

120 = 23·31·51·130·170
3315 = 20·31·51·131·171

Находим минимальные значения степеней простых чисел в разложениях.
Степени множителя 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.
Возводя множители в минимальные значения, получаем наибольший общий делитель:

НОД = 20·31·51·130·170 = ·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.
Возводя множители в максимальные значения, получаем наименьшее общее кратное:

НОК = 23·31·51·131·171 = ·8·3·5·13·17 = 26520.

Ответ

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

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

Разложение натурального числа 120 на простые множители
120 = 2*2*2*3*5;
120 = 23*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, то калькулятор выполнит решение задачи только одним способом – методом Евклида.

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

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

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

Меню