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

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

Делителем целого числа 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.
  • Алгоритм завершается, когда очередной остаток от деления окажется равен нулю.

    • Ещё Как найти

    Как найти площадь параллелограмма | Вопрос и Ответ
    Параллелограмм (от греч. parallelos — параллельный и gramme — линия) — это четырёхугольник, у которого противолежащие стороны попарно параллельны, т.е. лежат на параллельных

    Как найти точки пересечения графика линейной функции y = kx + b с осями координат | Вопрос и Ответ
    График линейной функции, заданной уравнением y = kx + b, обязательно пересекается с осью ординат Oy, а с осью абсцисс Ox пересекается при условии k≠0.

    Как найти похожие фотографии в Интернете | Вопрос и Ответ
    Найти похожие изображения в Интернете помогут представленные ниже сервисы. Для поиска похожих фотографий на сервисах можно загрузить свою фотографию или ввести ссылку на web-страницу с фотографией:

    Как найти момент сопротивления швеллера | Вопрос и Ответ
    Зачем нужен момент инерции сечения Несмотря на то, что наука о прочности давно уже шагнула вперёд, и давно уже развиваются многие её направления (строительная механика, механика

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

    Как найти неизвестный крайний член пропорции | Вопрос и Ответ
    Определение пропорции Пусть даны четыре отличных от нуля числа a, b, c и d таких, что a : b = c : d. Тогда равенство a : b = c : d называется пропорцией. Т.е. пропорция (лат.

    Как найти квадрат разности двух величин | Вопрос и Ответ
    Формулы сокращённого умножения Квадрат суммы двух величин равен квадрату первой плюс удвоенное произведение первой на вторую плюс квадрат второй: (a+b)2=a2+2ab+b2.

    Как найти момент сопротивления сложного сечения | Вопрос и Ответ
    Зачем нужен момент инерции сечения Несмотря на то, что наука о прочности давно уже шагнула вперёд, и давно уже развиваются многие её направления (строительная механика, механика

    Как найти площадь круга | Вопрос и Ответ
    Окружность — замкнутая плоская кривая, все точки которой одинаково удалены от данной точки (центра), лежащей в той же плоскости, что и кривая. Круг — часть плоскости,

    Как найти песню по словам | Вопрос и Ответ
    Для того, чтобы найти песню по словам, нужно прослушать её несколько раз, запомнить слова, затем открыть одну из этих ссылок: google.ru, yandex.ru. И написать прямо в строке поиска слова песни,

    Как найти песню по словам

    Комментарии