5.3.4. Нахождение наибольшего общего делителя (НОД) данных чисел

• Наибольшим общим делителем данных натуральных чисел называют наибольшее натуральное число, на которое делится каждое из этих чисел.
•  Наибольший общий делитель данных чисел равен произведению общих простых множителей в разложениях этих чисел. Пример. НОД(24, 42)=2·3=6, т. к. 24=2·2·2·3, 42=2·3·7, их общие простые множители 2 и 3.
•  Если натуральные числа имеют только один общий делитель-единицу, то эти числа называют взаимно простыми.

Пример 1

Найти НОД(15; 35).

Решение.

Разложим данные числа на простые множители.

 15=3∙5,               35=5∙7

Общий делитель чисел 15 и 35 – это число 5.

Ответ: НОД(15; 35)=5.

Пример 2

Найти НОД(72; 64).

Решение.

 Разложим числа 72 и 64 на простые множители.

72=2∙2∙2∙3∙3 или 72=2³∙3²,          64=2∙2∙2∙2∙2∙2 или 64=2⁶

Нужно взять произведение общих множителей: 2∙2∙2=2³=8.

Ответ: НОД(72; 64)=2³=8.

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

Пример 3

Найдите наибольший общий делитель разности чисел 69 и 19 и суммы чисел 36 и 39.

Решение.

Требуется найти НОД(50; 75). Разложим эти числа на простые множители.

50=2∙5² ;              75=3∙5²

Общий делитель 5 берем во второй степени.

НОД(50; 75)=5²=5∙5=25.

Ответ: НОД(50; 75)=25.