Азамат Бекетович Киреев
Наибольший общий делитель (НОД)

Полная версия

Правило. Если одно из данных чисел [36] является делителем другого числа [72], то оно [36] будет являться наибольшим общим делителем данных чисел [72 и 36].

Формулы, необходимые для алгоритма №1

Для вычисления по алгоритму №1 необходимо знать формулы

Замечание. Формулу a⁰=1 мы будем использовать «справа налево», то есть 1=a⁰.

Единицу мы будем представлять как 2⁰, как 3⁰, как 5⁰, как 7⁰, как 11⁰, …

1=2⁰, 1=3⁰, 1=5⁰, 1=7⁰, 1=11⁰, …

Алгоритм №1

Рекомендуемый способ нахождения

наибольшего общего делителя двух чисел

Алгоритм №1.

1) Разложить данные числа на простые множители;

2) выбрать наименьшие степени множителей из разложений данных чисел;

3) перемножить выбранные множители в наименьших степенях.

Кратко (для заучивания, нестрогое правило): разложить на множители, выбрать наименьшие степени, перемножить.

Пример 1. Найти НОД (18; 14).

1) Разложим на простые множители числа 18 и 14:

18=2×3²=2×3²×1= 2¹×3²×7⁰,

14=2×7=2¹×1×7¹=2¹×3⁰×7¹.

2) В обоих разложениях множитель 2 встречается в первой степени. Значит, выписываем множитель 2¹ (НАИМЕНЬШИЙ!!!).

Множитель 3 встречается во второй и нулевой степени, значит, выписываем 3⁰ (наименьший).

Множитель 7 встречается в первой и нулевой степени, значит, выписываем 7⁰ (наименьший).