Наибольший общий делитель
Общий делитель
Общий делитель чисел — это число, на которое делится без остатка каждое из данных натуральных чисел.
Пример.
Возьмём три числа: 6, 8 и 12. Каждое из них делится без остатка на 2, значит число 2 есть общий делитель чисел 6, 8 и 12.
Взаимно простые числа
Взаимно простые числа — это числа, не имеющие никаких общих делителей, кроме единицы.
У одних данных чисел может вовсе не быть общих делителей, кроме единицы, а у других их может быть несколько.
Пример.
Числа 27 и 32 — взаимно простые, они не имеют никаких общих делителей кроме 1.
Числа 42 и 105 имеют несколько общих делителей: 1, 3, 7 и 21.
НОД
Наибольший общий делитель — это самый большой из общих делителей. Среди всех общих делителей данных чисел всегда имеется наибольший.
Наибольший общий делитель данных чисел записывают так:
НОД (a, b, ...) = x,
где a, b, ... — данные числа, а x — наибольший общий делитель. Числа в круглых скобках могут быть указаны в любом порядке.
Пример.
Из всех общих делителей чисел 42 и 105, наибольшим общим делителем является число 21:
НОД (42, 105) = 21.
Наибольший общий делитель взаимно простых чисел — единица.
Пример.
НОД (27, 32) = 1.
Как найти наибольший общий делитель
Есть два способа нахождения НОД: с помощью разложения данных чисел на простые множители и методом последовательного деления.
Поиск НОД с помощью разложения на простые множители
Чтобы найти НОД данных натуральных чисел, нужно каждое из данных чисел разложить на простые множители и найти произведение общих простых множителей, взяв каждый из них с наименьшим показателем степени.
Пример.
Найти НОД (120, 252).
Решение. Раскладываем числа 120 и 252 на простые множители:
Разложив каждое число на простые множители, находим произведение общих множителей, взяв каждый из них с наименьшим показателем степени:
22 · 3 = 12.
Ответ: НОД (120, 252) = 12.
Пример.
Найти НОД (8, 9).
Решение. Раскладываем 8 и 9 на простые множители:
Числа 8 и 9 являются взаимно простыми, поэтому их наибольший общий делитель — единица.
Ответ: НОД (8, 9) = 1.
Метод последовательного деления
Суть данного метода заключается в делении полученного (не нулевого) остатка на предыдущий делитель.
Итак, чтобы найти НОД двух натуральных чисел нужно:
- разделить большее число на меньшее. Если большее число делится без остатка на меньшее, то меньшее число и будет НОД данных чисел;
- если в результате деления получился остаток, то нужно предыдущий делитель разделить на полученный остаток;
- выполняем пункт 2 до тех пор, пока в остатке не получится нуль. Последний делитель и будет НОД данных чисел.
Пример.
Найти НОД (12, 24).
Решение. Так как 24 делится на 12, то число 12 является НОД чисел 12 и 24.
Ответ: НОД (12, 24) = 12.
Пример.
Найти НОД (210, 72).
Решение. Делим большее число на меньшее:
1) 210 : 72 = 2 (остаток 66).
Делим предыдущий делитель (т. е. 72) на полученный остаток (т. е. 66):
2) 72 : 66 = 1 (остаток 6).
Так как остаток не нулевой, делим предыдущий делитель на полученный остаток:
3) 66 : 6 = 11 (остаток 0).
В остатке 0, последний делитель равен 6, значит НОД (210, 72) = 6.
Ответ: НОД (210, 72) = 6.
Чтобы с помощью данного метода найти НОД трёх и более чисел, необходимо найти сначала НОД каких-нибудь двух чисел из нескольких данных, затем найти НОД найденного делителя и какого-нибудь третьего данного числа и т. д.
Пример.
Найти НОД (120, 252, 42).
Решение. Сначала найдём НОД каких-нибудь двух чисел из данных, например, 120 и 252:
1) 252 : 120 = 2 (остаток 12);
2) 120 : 12 = 10 (остаток 0).
НОД (120, 252) = 12. Теперь найдём НОД найденного наибольшего делителя (12) и оставшегося третьего числа (42):
1) 42 : 12 = 3 (остаток 6);
2) 12 : 6 = 2 (остаток 0).
Последний делитель равен 6, значит НОД (120, 252, 42) = 6.
Ответ: НОД (120, 252, 42) = 6.