Наибольший общий делитель (НОД) чисел a и b - это наибольшее число, на которое делятся без остатка числа a и b.
Среди всех способов нахождения наибольшего общего делителя для двух чисел алгоритм Евклида наиболее удобный и простой.
Нахождения НОД и НОК по алгоритму Евклида методом деления
Как известно, деление с остатком целых чисел a - делимое и b - делитель, где b ≠ 0, подразумевает нахождение таких целых чисел q и r, что выполняется равенство:
a = b ∙ q + r, где
q - называется неполным частным,
r - остаток от деления, который не может быть отрицательным числом и по модулю не может быть больше делителя.
Суть метода состоит в том, что сначала выбираем наибольшее из двух чисел, для которых требуется найти НОД и делим большее число на меньшее. Если остаток от деления не равен нулю, делим делитель на остаток от деления, так продолжаем до тех пор, пока остаток от деления не будет равен нулю.
Пример 1
Найдем НОД (36; 30), для этого сначала найдем остаток от деления 36 на 30
36 : 30 = 1 (остаток 6), так как 36 = 30 ∙ 1 + 6, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 30 на 6
30 : 6 = 5 (остаток 0) так как 30 = 6 ∙ 5 + 0, остаток от деления равен нулю, значит НОД равен предыдущему остатку от деление 6
Ответ: НОД (36; 30) = 6
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (36; 30) = (36 ∙ 30) : 6 = 180
Пример 2
Найдем НОД (176; 36), для этого сначала найдем остаток от деления 176 на 36
176 : 36 = 4 (остаток 32) так как 176 = 36 ∙ 4 + 32, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 36 на 32
36 : 32 = 1 (остаток 4) так как 36 = 32 ∙ 1 + 4, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 32 на 4
32 : 4 = 8 (остаток 0) так как 32 = 4 ∙ 8 + 0, остаток от деления равен нулю, значит НОД равен предыдущему остатку от деление 4
Ответ: НОД (176; 36) = 4
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (176; 36) = (176 ∙ 36) : 4 = 1584
Нахождения НОД и НОК по алгоритму Евклида методом вычитания
Суть метода вычитания состоит в том, что необходимо из большего числа вычитать меньшее, если результат вычитания не равен нулю,
тогда уменьшаемое заменяем на получившуюся разность, если разность равна нулю, то НОД равен предыдущему значению разности.
Приведем примеры:
Пример 1
Найдем НОД (36; 30)
36 - 30 = 6
30 - 6 = 24
24 - 6 = 18
18 - 6 = 12
12 - 6 = 6
6 - 6 = 0
Ответ: НОД (36; 30) = 6
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (36; 30) = (36 ∙ 30) : 6 = 180
Пример 2
Найдем НОД (176; 36)
176 - 36 = 140
140 - 36 = 104
104 - 36 = 68
68 - 36 = 32
36 - 32 = 4
32 - 4 = 28
28 - 4 = 24
24 - 4 = 20
20 - 4 = 16
16 - 4 = 12
12 - 4 = 8
8 - 4 = 4
4 - 4 = 0
Ответ: НОД (176; 36) = 4
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (176; 36) = (176 ∙ 36) : 4 = 1584