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

Возьмём три числа: 60, 90 и 120. Каждое из них делится на 30. Значит число 30 есть делитель каждого из них. Принято говорить, что число 30 есть общий делитель чисел: 60, 90 и 120.

В дальнейшем нам часто придётся искать общий делитель для двух, трёх и т. д. чисел. Запомним, что общим делителем нескольких чисел называется число, на которое все данные числа делятся без остатка.

Заметим, что у некоторых чисел может вовсе не быть общих делителей, кроме единицы, а у иных их может быть несколько. Например, числа 27 и 32 не имеют общих делителей, кроме 1;

числа 25 и 35 имеют общие делители: 1 и 5;

числа 42 и 105 имеют общие делители: 1, 3, 7 и 21;

числа 21, 35 и 49 имеют общие делители: 1 и 7.

Числа, не имеющие общих делителей (кроме единицы), называются взаимно простыми.

Возьмём два числа: 60 и 75, и посмотрим, какие у них общие делители.

Число 60 делится на 1,2, 3, 4, 5, 6, 10, 12, 15, 20, 30;

число 75 делится на 1, 3, 5, 15, 25.

Значит у этих чисел только четыре общих делителя, это 1, 3, 5 и 15.

Наибольший из этих общих делителей есть число 15, которое и называется наибольшим общим делителем чисел 60 и 75.

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

Выше мы указали, какие числа называются взаимно простыми; теперь ту же мысль мы выразим иначе.

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

Как найти наибольший общий делитель нескольких чисел?

Возьмём сначала два числа: 63 и 84, и найдём их наибольший общий делитель. Разложим эти числа на простые множители:

63 = 3•3•7; 84 = 2•2•3•7.

Чтобы оба эти числа делились на некоторое третье число, необходимо, чтобы в это последнее входили множители, общие двум данным числам; наибольший общий делитель получится от перемножения всех простых общих множителей. Общими множителями у данных чисел являются 3 и 7. Значит, наибольший общий делитель этих чисел (63 и 84) будет 21. Сокращённо это записывают так:

НОД (63 и 84) = 21.

Рассмотрим ещё один пример. Найдём наибольший общий делитель трёх чисел: 420, 630 и 1 260. Разложим каждое из этих чисел на простые множители:

Выпишем множители, общие этим трём числам. Число 2 входит общим множителем во все три данные числа, но только один раз; второй раз множитель 2 входит в первое и третье число, но не входит в 630. Число 3 один раз входит во все данные числа, но второй раз входит только в последние два числа. Числа 5 и 7 входят множителями во все данные числа. Значит, общими множителями являются следующие: 2, 3, 5, 7. Их произведение, т. е. 210, и будет наибольшим общим делителем данных чисел.

Отсюда вытекает правило:

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