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

еоретический материал

      В таблице приведем два способа определения НОД.

      Алгоритм №0.

      Не является рациональным способом нахождения наибольшего общего делителя двух чисел

      Выпишем все делители чисел 32 и 24.

      Делители числа 32: 1, 2, 4, 8, 16, 32.

      Делители числа 24: 1, 2, 3, 4, 6, 8, 12, 24.

      Общими делителями 24 и 32 являются: 1, 2, 4, 8.

      Наибольший из них – 8. Обозначается НОД(24;32)=8.

      Замечание. Вышеизложенный алгоритм №0 не является рациональным способом нахождения НОД (им можно воспользоваться в том случае если вы забыли способы нахождения НОД).

      Определение 3. Натуральные числа a и b называют взаимно простыми, если их наибольший общий делитель равен 1, то есть НОД(a; b) = 1.

      Иначе выражаясь, если числа a и b не имеют никаких общих делителей, кроме 1, то они взаимно просты.

      Пример 3.

      1) Числа 2 и 5 взаимно простые (и сами они простые);

      2) 2 и 9 взаимно простые (2 – простое, 9 – составное);

      3) 8 и 9 взаимно простые (и оба они составные);

      Замечание. Как видно из случаев, приведенных в примере 2, понятия «простые числа» и «взаимно простые числа» не имеют особой связи между собой.

      Правило. Если одно из данных чисел [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⁰ (наименьший).

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

      Ответ: НОД(18; 14)=2.

      Замечание. Нулевая степень в разложении числа обозначает, что данный множитель входит в разложение числа ноль раз. Запись 18=2¹×3²×7⁰ означает, что множитель 7 входит ноль раз в разложение числа 18.

      Пример 2. Найти НОД (36; 30).

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

      36=2²×3²= 2²×3²×1= 2²×3²×5⁰,

      30=2×3×5=2¹×3¹×5¹.

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

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

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

      3) 2¹×3¹×5⁰=2×3×1=6

      Ответ: НОД(36; 30)=6.

      Пример 3. Найти НОД (9; 10).

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

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

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