Нахождение НОК и НОД двух натуральных чисел

Что такое НОК и НОД двух натуральных чисел

Натуральными числами называют числа, которые используются при счете – 1, 2, 3, 16, 25, 101, 2560 и далее до бесконечности. Ноль, отрицательные и дробные или нецелые числа не относятся к натуральным.

Свойства НОК и НОД для натуральных чисел a и b

• \(НОД (a, b) = НОД (b, a);\)
• \(НОК (a, b) = НОК (b, a);\)
• \(НОК\;(a,b)=\frac{a\;\times\;b}{НОД\;(a,b)}.\)

Особенности вычисления, алгоритм Евклида

Рассмотрим два способа определения НОД и НОК с помощью алгоритма Евклида:

• Способ деления.

При делении целых чисел с остатком, где a - делимое, b – делитель (b не равно 0) находят целые числа q и r согласно равенству \(a=b\times\) q+r, в котором q – неполное частное, r – остаток при делении (не отрицательное, по модулю меньше делителя).

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

\(20=12\times1+8\), так как остаток не равняется нулю, продолжаем деление. Делим 12 на 8 и получаем 1 и 4 в остатке. Записываем: \(12=8\times1+4\) и по аналогии делим 8 на 4 и получаем 2 и 0 в остатке. НОД равен остатку, предшествующему нулю.

НОД (12;20) = 4

НОК получаем согласно свойству \(НОК (a, b) = НОК\;(a,b)=\frac{a\;\times\;b}{НОД\;(a,b)}.\) Подставляем числовые значения:

НОК (12; 20) = \(12\times20\div4=60\)

НОК (12;20) = 60

• Способ вычитания.

Здесь повторяется цикл вычитания из наибольшего числа меньшего числа до момента, пока разность не станет равна нулю. НОД равен предшествующей нулю разности.

20 – 12 = 8 (разность не равна нулю, продолжаем)

12 – 8 = 4

8 – 4 = 4

4 – 4 = 0

НОД (12;20) = 4

НОК находим также, как и при методе деления.

Правило нахождения наибольшего общего делителя (НОД)

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

1. Разложить числа на простые множители.
2. Найти общий множитель одного и другого числа.
3. Перемножить общие множители, если их несколько, и их произведение будет НОД.

\(24=2\times2\times2\times3\)

\(36=2\times2\times3\times3\)

Правильно записать следующим образом:

\(НОД (24;36)=2\times3=6\)

Правило нахождения наименьшего общего кратного (НОК)

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

1. Наибольшее из чисел, а затем остальные разложить на простые множители.
2. Выделить те множители, которые отсутствуют у наибольшего.
3. Перемножить множители п. 2 и множители наибольшего числа, получить НОК.

\(12=2\times2\times3\)

\(9=3\times3\) (видим, что у числа 12 отсутствует одна тройка)

Правильно записать следующим образом:

\(НОК (9;12)=2\times2\times3\times3=36\)