28982 автора и 62 редактора ответили на 85243 вопроса,
разместив 135214 ссылок на 43429 сайтов, присоединяйтесь!

Как найти наибольший общий делитель (НОД) нескольких целых чисел?

РедактироватьВ избранноеПечать

Делителем целого числа m называется любое целое число q, на которое m делится без остатка.

 

Общим делителем нескольких чисел называется такое число, которое является делителем каждого из них. Например, числа 36, 60, 42 имеют общие делители 2, 3 и 6.

 

Наибольший общий делитель (НОД) для двух целых чисел m и n — это наибольшее из целых чисел, на которые m и n делятся без остатка. Например: для чисел 70 и 105 наибольший общий делитель равен 35.

 

Для наибольшего общего делителя чисел m и n применяются следующие математические обозначения:

  • НОД(m, n)
  • (m, n)
  • gcd(m, n) — от англ. Greatest Common Divisor.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n отлично от нуля.

 

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.

 

Чтобы найти наибольший общий делитель (НОД) нескольких чисел надо:

  1. Представить каждое число как произведение его простых множителей, например: 
    360 = 2 · 2 · 2 · 3 · 3 · 5.
  2. Записать степени всех простых множителей:
    360 = 2 · 2 · 2 · 3 · 3 · 5 = 23 · 32 · 51.
  3. Выписать все общие делители (множители) этих чисел.
  4. Выбрать наименьшую степень каждого из них, встретившуюся во всех произведениях.
  5. Перемножить эти степени.

Однако такой метод поиска НОД весьма трудоемок. С древности известен более удобный метод нахождения НОД, называемый алгоритмом Евклида.

  1. Пусть m>n. Найдем остаток r от деления m на n.
  2. Если r = 0 (т.е. m делится на n), то НОД(m, n) = n.
  3. В противном случае вместо чисел m и n надо взять числа n и r и перейти к п. 1.
  4. Алгоритм завершается, когда очередной остаток от деления окажется равен нулю. 

Источники:

  • ru.wikipedia.org — Википедия: Наибольший общий делитель
  • bymath.net — сайт «Вся элементарная математика», раздел «Общий делитель. Наибольший общий делитель»
  • ru.wikipedia.org — Википедия: Алгоритм Евклида 

Дополнительно на Геноне: 

Последнее редактирование ответа: 22.05.2012

  • Оставить отзыв

    Оставить отзыв

РедактироватьВ избранноеПечать

Похожие вопросы

«Как найти наибольший общий делитель (НОД) нескольких целых чисел»

В других поисковых системах:

GoogleЯndexRamblerВикипедия

В соответствии с пользовательским соглашением администрация не несет ответственности за содержание материалов, которые размещают пользователи. Для урегулирования спорных вопросов и претензий Вы можете связаться с администрацией сайта genon.ru. Размещенные на сайте материалы могут содержать информацию, предназначенную для пользователей старше 18 лет, согласно Федерального закона №436-ФЗ от 29.12.2010 года "О защите детей от информации, причиняющей вред их здоровью и развитию". Обращение к пользователям 18+.