Вопросы и Ответы

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

0

Делителем целого числа 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 отлично от нуля.

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

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

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

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

     Изменить 

    Ещё Как найти

    Как найти экстремумы функции нескольких переменных | Вопрос и Ответ
    Что такое экстремум функции и каково необходимое условие экстремума? Экстремумом функции называется максимум и минимум функции. Необходимое условие максимума и

    Как найти площадь трапеции | Вопрос и Ответ
    Трапеция - четырёхугольник, у которого две стороны параллельны (основания трапеции), а две другие - непараллельны (боковые стороны трапеции). Отрезок, соединяющий середины боковых сторон,

    Как найти длину катета по двум другим сторонам прямоугольного треугольника | Вопрос и Ответ
    Катетами называют две стороны прямоугольного треугольника, которые прилегают к прямому углу. Гипотенузой называют сторону прямоугольного треугольника, которая противолежит прямому углу.

    Как найти точки экстремума функции | Вопрос и Ответ
    Что такое экстремум функции и каково необходимое условие экстремума? Экстремумом функции называется максимум и минимум функции. Необходимое условие максимума и

    Как найти углы в прямоугольном треугольнике, если известны две стороны | Вопрос и Ответ
    Тригонометрия — это раздел математики, в котором изучаются тригонометрические функции, их свойства, взаимосвязи и применение. Слово «тригонометрия» образовано от

    Как найти корень в слове | Вопрос и Ответ
    Морфемика — это раздел науки о языке, в котором изучается состав (строение) слова. См. Как разобрать слово по составу? Каждое слово можно разделить на минимальные значимые

    Как найти косинус угла, если известен синус | Вопрос и Ответ
    Тригонометрия — это раздел математики, в котором изучаются тригонометрические функции, их свойства, взаимосвязи и применение. Слово «тригонометрия» образовано от

    Как найти объем конуса | Вопрос и Ответ
    Объем геометрической фигуры — количественная характеристика пространства, занимаемого телом или веществом. Объём тела или вместимость сосуда определяется его формой и линейными размерами.

    Как найти тангенс | Вопрос и Ответ
    Тригонометрия — это раздел математики, в котором изучаются тригонометрические функции, их свойства, взаимосвязи и применение. Слово «тригонометрия» образовано от

    Как найти площадь произвольного четырехугольника | Вопрос и Ответ
    Площадь любого четырехугольника можно найти по формуле: S = d1·d2·sinφ, где d1 и d2 — длины двух диагоналей четырехугольника, а φ —

    Фото Наука и образование

     Изменить 
    Как найти площадь произвольного четырехугольника