Skraftix.ru
Наибольший общий делитель Наименьшее общее кратное

Наибольший общий делитель

Общий делитель

Общий делитель чисел — это число, на которое делится без остатка каждое из данных натуральных чисел.

Пример.

Возьмём три числа: 6, 8 и 12. Каждое из них делится без остатка на 2, значит число 2 есть общий делитель чисел 6, 8 и 12.

Взаимно простые числа

Взаимно простые числа — это числа, не имеющие никаких общих делителей, кроме единицы.

У одних данных чисел может вовсе не быть общих делителей, кроме единицы, а у других их может быть несколько.

Пример.

Числа 27 и 32 — взаимно простые, они не имеют никаких общих делителей кроме 1.

Числа 42 и 105 имеют несколько общих делителей: 1, 3, 7 и 21.

НОД

Наибольший общий делитель — это самый большой из общих делителей. Среди всех общих делителей данных чисел всегда имеется наибольший.

Наибольший общий делитель данных чисел записывают так:

НОД (ab, ...) = 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.

Метод последовательного деления

Суть данного метода заключается в делении полученного (не нулевого) остатка на предыдущий делитель.

Итак, чтобы найти НОД двух натуральных чисел нужно:

  1. разделить большее число на меньшее. Если большее число делится без остатка на меньшее, то меньшее число и будет НОД данных чисел;
  2. если в результате деления получился остаток, то нужно предыдущий делитель разделить на полученный остаток;
  3. выполняем пункт 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.