Наибольший общий делитель (НОД) нам известен из школьного курса математики. Тема вызывает особое к себе отношение, в связи с активным применением за пределами школьного кабинета. Мы знаем два способа вычисления наибольшего общего делителя, и на основе этих материалов можем попробовать определиться с более удобными методами.
Метод перебора общих делителей.
- Определяем все возможные делители числа а;
- Определяем все возможные делители числа b;
- Среди них находим делители, которые являются общими;
- Среди количества общих делителей определяем самое наибольшее число, оно и будет являться наибольшим общим делителем чисел а и b — НОД (a, b).
Пример: найдите НОД (24; 60).
Введём обозначения: делители числа обозначим буквой Д.
Д (24) = {1; 2;3; 4;6;8; 12; 24};
Д (60) = {1; 2; 3; 4;5; 6;10; 12; 15; 20; 30;60}.
Д (24; 60) = {1; 2; 4;12}.
НОД (24; 60) = 12.
Такой способ может быть удобен в тех случаях, когда количество делителей хотя бы у одного из чисел невелико.
Метод нахождения НОД натуральных чисел с помощью разложения на простые множители.
- Разложим числа на простые множители.
- Подчеркиваем общие простые множители.
- Находим произведение подчеркнутых простых множителей у одного числа — это будет являться наибольшим общим делителем чисел а и b — НОД (a, b).
Пример: найдите НОД (24; 60).
Произведём разложение на простые множители числа
24 = 2·2·2·3, 60 = 2·2·5·3.
НОД (36, 48) = 2·2·3 = 12 [1, c. 24]
Данный способ будет удобен только для разложения небольших чисел на простые множители.
Рассмотрим другой способ нахождения общего делителя двух чисел. Он называется алгоритмом Евклида.
Алгоритм Евклида нахождения НОД двух натуральных чисел вычитанием.
- Из большего числа вычтем меньшее число.
- Если получается нуль, то числа равны друг другу и будут являться НОД.
- Если результат вычитания не равен нулю, то большее число заменяется на результат вычитания.
- Переход к пункту 1.
Пример: найти НОД (24; 60).
Решение: найдем разность чисел 60 и 24: 60–24 = 36. Затем большее число заменим на результат вычитания. Теперь найдем НОД (24; 36).
36–24 = 12. Далее заменим 36 на 12. Затем находим НОД (24; 12).
24–12 = 12. Заменив 24 на 12, находим НОД (12; 12).
12–12 = 0, так как разность равна 0, то НОД — это уменьшаемое или вычитаемое.
НОД (24; 60) = НОД (24; 36) = НОД (24; 12) = НОД (12; 12) = 12.
Рассмотренный метод нахождения наибольшего общего делителя имеет свои особенности. Например, в случае нахождения НОД (300; 5) придётся исполнить 60 операций вычитания. Поэтому рассмотрим другой алгоритм Евклида, который может способствовать ускорению вычислительных действий.
Алгоритм Евклида нахождения НОД двух натуральных чисел делением.
- Большее число делится на меньшее.
- Если делится без остатка, то меньшее число и есть наибольший общий делитель.
- Если есть остаток, то большее число заменяем на остаток от деления.
4. Переход к пункту 1.
Пример: найти НОД (432; 111).
Решение: разделив 432 на 111, получаем равенство 432 = 111*3+99.
Выполнив деление 111 на 99, получаем равенство 111 = 99*1+12.
Деление 99 на 12 дает равенство 99 = 12*8+3.
12 делится на 3 без остатка, то есть 12 = 3*4, следовательно НОД (432; 111) = 3 [2, c 88].
Бинарный алгоритм Евклида нахождения НОД двух натуральных чисел.
Бинарный алгоритм Евклида вычисления НОД несёт в себе более быстрый характер. Рассмотрим структуру данного алгоритма:
- Если оба числа a и b чётные, то НОД (a; b) = 2*НОД (a/2; b/2);
- Если a нечётное, b чётное, то НОД (a; b) = НОД (a; b/2);
- Если оба числа a и b нечётные a > b, то НОД (a; b) = НОД ((a-b); b);
- Если a = b, то НОД (a; b) =a.
Пример: найти НОД (1118; 2064).
Решение: НОД (1118; 2064) = 2*НОД (559; 1032) = 2*НОД (559; 516) = 2*НОД (559;258) = 2*НОД (559; 129) = 2*НОД (430; 129) = 2*НОД (215; 139) = 2*НОД (86; 129) =
= 2*НОД (43; 129) = 2*НОД (43; 86) = 2*НОД (43; 43) = 2*43 = 86.
НОД (1118; 2064) = 86 [3].
Анализируя различные методы нахождения наибольшего общего делителя, можно прийти к мнению, что идеальных методов не бывает. Каждый метод характеризуется своими положительными и отрицательными сторонами. В каждом конкретном случае, мы должны определиться с выбором наиболее эффективного метода для того, чтобы максимально бережно отнестись к затраченному времени, которого на экзаменах как всегда будет не хватать.
Литература:
1. Виленкин Н. Я. и др. Математика, 6 класс: учебник для общеобразовательных учреждений. — М.: Мнемозина, 2013. — 288 с.
2. Макарычев Ю. Н., Миндюк Н. Г. Алгебра: Дополнительные главы к школьному учебнику 8 кл.: учебное пособие для школ и классов с углубленным изучением математики.- М.: Просвещение, 1996.- 207 с.
3. Щетников А. И. Алгоритм Евклида и непрерывные дроби. — Новосибирск: АНТ, 2003 г.-103 с.
