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=23∙32,          64=2∙2∙2∙2∙2∙2 или 64=26

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

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

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

     

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

    Решение.

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

    50=2∙52 ;              75=3∙52

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

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

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

     

    Метки: