Нахождение наибольшего общего делителя различными методами | Статья в журнале «Юный ученый»

Отправьте статью сегодня! Журнал выйдет 26 июня, печатный экземпляр отправим 30 июня.

Опубликовать статью в журнале

Авторы: , ,

Научные руководители: ,

Рубрика: Математика: алгебра и начала анализа, геометрия

Опубликовано в Юный учёный №1 (10) февраль 2017 г.

Дата публикации: 26.01.2017

Статья просмотрена: 2747 раз

Библиографическое описание:

Нахождение наибольшего общего делителя различными методами / П. Р. Красикова, А. В. Лиджиева, А. Н. Алиева [и др.]. — Текст : непосредственный // Юный ученый. — 2017. — № 1 (10). — С. 46-47. — URL: https://moluch.ru/young/archive/10/742/ (дата обращения: 17.06.2021).



Наибольший общий делитель (НОД) нам известен из школьного курса математики. Тема вызывает особое к себе отношение, в связи с активным применением за пределами школьного кабинета. Мы знаем два способа вычисления наибольшего общего делителя, и на основе этих материалов можем попробовать определиться с более удобными методами.

Метод перебора общих делителей.

  1. Определяем все возможные делители числа а;
  2. Определяем все возможные делители числа b;
  3. Среди них находим делители, которые являются общими;
  4. Среди количества общих делителей определяем самое наибольшее число, оно и будет являться наибольшим общим делителем чисел а и 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.

Такой способ может быть удобен в тех случаях, когда количество делителей хотя бы у одного из чисел невелико.

Метод нахождения НОД натуральных чисел с помощью разложения на простые множители.

  1. Разложим числа на простые множители.
  2. Подчеркиваем общие простые множители.
  3. Находим произведение подчеркнутых простых множителей у одного числа — это будет являться наибольшим общим делителем чисел а и 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. Из большего числа вычтем меньшее число.
  2. Если получается нуль, то числа равны друг другу и будут являться НОД.
  3. Если результат вычитания не равен нулю, то большее число заменяется на результат вычитания.
  4. Переход к пункту 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 операций вычитания. Поэтому рассмотрим другой алгоритм Евклида, который может способствовать ускорению вычислительных действий.

Алгоритм Евклида нахождения НОД двух натуральных чисел делением.

  1. Большее число делится на меньшее.
  2. Если делится без остатка, то меньшее число и есть наибольший общий делитель.
  3. Если есть остаток, то большее число заменяем на остаток от деления.

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].

Бинарный алгоритм Евклида нахождения НОД двух натуральных чисел.

Бинарный алгоритм Евклида вычисления НОД несёт в себе более быстрый характер. Рассмотрим структуру данного алгоритма:

  1. Если оба числа a и b чётные, то НОД (a; b) = 2*НОД (a/2; b/2);
  2. Если a нечётное, b чётное, то НОД (a; b) = НОД (a; b/2);
  3. Если оба числа a и b нечётные a > b, то НОД (a; b) = НОД ((a-b); b);
  4. Если 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 с.

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


Похожие статьи

Исследование алгоритмов генерации простых чисел

Для чисел специального вида разработаны алгоритмы проверки на простоту, которые невозможно применить к обычным числам.

4. Найти простое число, которое будет делителем заданного натурального числа (разложить заданное натуральное число на множители).

Теория чисел в криптографии | Статья в журнале...

наибольший общий делитель целых чисел ; — целое число делит нацело целое число . Диофантовы уравнения — уравнения, в которых

Абонент B генерирует два больших простых числа p и q и вычисляет произведение , выбирает натуральное , взаимно простое с и и...

Разработка способа представления длинных чисел в памяти...

Умножение чисел путем последовательного сложения, с учетом длины чисел, может занять значительное количество времени. В связи с этим был реализован алгоритм поразрядного умножения, который заключается в следующем

Изложение теории делимости в УМК «Математика 5–6» авторского...

Изучением делимости чисел занимался еще Пифагор (VI в. до н. э.) и его ученики. Они изучали всю красоту и природу чисел в целом, занимались изучением совершенных чисел, т. е. чисел, равных сумме всех его делителей, таким образом, уже знали делители и кратные чисел.

Применение метода математической индукции к решению задач на...

В математических олимпиадах часто встречаются достаточно трудные задачи на доказательство делимости натуральных чисел. Перед школьниками возникает проблема: как найти универсальный математический метод, позволяющий решать подобные задачи?

Сложение коммутативных полугрупп натуральных чисел...

Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся натуральное число, большее чем .

Для вычисления результата сложения двух коммутативных полугрупп натуральных чисел, где а — нечетное число, а b — четное число и...

Роль больших простых чисел в современной криптографии

Простые числа — это целые натуральные числа больше единицы, которые имеют ровно 2 натуральных делителя (только 1 и

Но они мало встречаются среди натуральных чисел. Определяем общее количество всех 32-битных натуральных чисел и 32-битных простых чисел.

Основные термины (генерируются автоматически): число...

. Аналогично разложим число3500 на множители: . Значит, принадлежит множеству делителей числа 3500: . Учитывая спецзадачу № 1 и факт, что — простое число, делаем вывод: , остальные значения являются составными числами.

число, полугруппа, сложение, результат сложения, множество...

К примеру, инвариантом может быть число, набор чисел, четность какого-либо числа и другое.

Решение. Нельзя. При прибавлении одинаковых целых чисел к любым двум из имеющихся не меняется четность общей суммы всех чисел.

Похожие статьи

Исследование алгоритмов генерации простых чисел

Для чисел специального вида разработаны алгоритмы проверки на простоту, которые невозможно применить к обычным числам.

4. Найти простое число, которое будет делителем заданного натурального числа (разложить заданное натуральное число на множители).

Теория чисел в криптографии | Статья в журнале...

наибольший общий делитель целых чисел ; — целое число делит нацело целое число . Диофантовы уравнения — уравнения, в которых

Абонент B генерирует два больших простых числа p и q и вычисляет произведение , выбирает натуральное , взаимно простое с и и...

Разработка способа представления длинных чисел в памяти...

Умножение чисел путем последовательного сложения, с учетом длины чисел, может занять значительное количество времени. В связи с этим был реализован алгоритм поразрядного умножения, который заключается в следующем

Изложение теории делимости в УМК «Математика 5–6» авторского...

Изучением делимости чисел занимался еще Пифагор (VI в. до н. э.) и его ученики. Они изучали всю красоту и природу чисел в целом, занимались изучением совершенных чисел, т. е. чисел, равных сумме всех его делителей, таким образом, уже знали делители и кратные чисел.

Применение метода математической индукции к решению задач на...

В математических олимпиадах часто встречаются достаточно трудные задачи на доказательство делимости натуральных чисел. Перед школьниками возникает проблема: как найти универсальный математический метод, позволяющий решать подобные задачи?

Сложение коммутативных полугрупп натуральных чисел...

Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся натуральное число, большее чем .

Для вычисления результата сложения двух коммутативных полугрупп натуральных чисел, где а — нечетное число, а b — четное число и...

Роль больших простых чисел в современной криптографии

Простые числа — это целые натуральные числа больше единицы, которые имеют ровно 2 натуральных делителя (только 1 и

Но они мало встречаются среди натуральных чисел. Определяем общее количество всех 32-битных натуральных чисел и 32-битных простых чисел.

Основные термины (генерируются автоматически): число...

. Аналогично разложим число3500 на множители: . Значит, принадлежит множеству делителей числа 3500: . Учитывая спецзадачу № 1 и факт, что — простое число, делаем вывод: , остальные значения являются составными числами.

число, полугруппа, сложение, результат сложения, множество...

К примеру, инвариантом может быть число, набор чисел, четность какого-либо числа и другое.

Решение. Нельзя. При прибавлении одинаковых целых чисел к любым двум из имеющихся не меняется четность общей суммы всех чисел.

Задать вопрос