Что такое делитель целого числа

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

Алгоритм завершается, когда очередной остаток от деления окажется равен нулю.

Ещё Что такое

Что такое сепаратизм | Вопрос и Ответ
Сепаратизм изначально происходит от латинского слова separare, которое переводится как разделять или же отделять. Слово сепаратизм есть в составе многих западноевропейских языков и имеет в них

Что такое гражданство | Вопрос и Ответ
Гражданство — устойчивая правовая связь человека и государства, выражающаяся в наличии взаимных прав, обязанностей и ответственности.Гражданство является одним из институтов конституционного

Что такое плоские бородавки | Вопрос и Ответ
Бородавки — доброкачественные новообразования кожи, вызываемые различными типами вируса папилломы человека. Преобладающий возраст – детский, юношеский. Бородавки способствую снижению

Что такое гидроколонотерапия | Вопрос и Ответ
Акне (угревая сыпь) – одно из самых распространенных кожных заболеваний, при котором происходит воспаление сальных желез лица, груди и спины. Постакне – это рубцы и красные

Что такое броматология | Вопрос и Ответ
Нутрициология — это одно из направлений науки о питании человека и животных (от позднелат. nutrio — питание, пища и logos — слово). Нутрициология является

Что такое yo-yo | Вопрос и Ответ
Йо-йо - одна из древнейших игрушек на Земле. Существует много версий касательно родины йо-йо, прототипы игрушки существовали в Древнем Китае около двух тысяч лет назад, однако доказательств немного.

Что такое теория игр | Вопрос и Ответ
Теория игр (русский эквивалент английского theory of games) - математическая теория, предсказания результатов игр, в которых участники не имеют полной информации о намерениях друг друга.

Что такое валентность | Вопрос и Ответ
Валентность (от лат. valentia — сила) в общем случае — способность объекта взаимодействовать с другими объектами. Валентность в химии — способность атомов

Что такое вирус полиомиелита | Вопрос и Ответ
Полиомиелит (poliomyelitis, Infantile Paralysis, Polio; polio (греч.) — серый, myelos — мозг) — острая вирусная инфекция, поражающая нервную систему (серое вещество спинного

Что такое антропогенный рельеф | Вопрос и Ответ
Антропогенный рельеф, рельеф, измененный или созданный деятельностью человека. Антропогенные формы рельефа впервые возникли в то время, когда охотничьи племена начали рыть ямы для ловли зверей,

Что такое антропогенный рельеф

Комментарии