Что такое наиболее общий делитель
Наибольший общий делитель (НОД): определение, примеры и свойства
Что такое общие делители
Чтобы понять, что из себя представляет наибольший общий делитель, сначала сформулируем, что вообще такое общий делитель для целых чисел.
В статье о кратных и делителях мы говорили, что у целого числа всегда есть несколько делителей. Здесь же нас интересуют делители сразу некоторого количества целых чисел, особенно общие (одинаковые) для всех. Запишем основное определение.
Общим делителем нескольких целых чисел будет такое число, которое может быть делителем каждого числа из указанного множества.
Зная свойства делимости, мы можем утверждать, что любое целое число можно разделить на единицу и минус единицу, значит, у любого набора целых чисел уже будет как минимум два общих делителя.
Что такое наибольший общий делитель (НОД)
Переходим к формулировке основного определения.
Наибольшим общим делителем нескольких чисел является самое большое целое число, которое делит все эти числа.
Для трех и более чисел определение наибольшего общего делителя будет почти таким же.
Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.
Проверить правильность данного утверждения можно с помощью записи всех делителей этих чисел и последующего выбора наибольшего из них.
На практике часто встречаются случаи, когда наибольший общий делитель равен одному из чисел. Это происходит тогда, когда на данное число можно разделить все остальные числа (в первом пункте статьи мы привели доказательство этого утверждения).
Основные свойства НОД и алгоритм Евклида
У наибольшего общего делителя есть некоторые характерные свойства. Сформулируем их в виде теорем и докажем каждое из них.
Отметим, что данные свойства сформулированы для целых чисел больше нуля, а делители мы рассмотрим только положительные.
Данное свойство следует из самого определения НОД и не нуждается в доказательствах.
Докажем это утверждение.
Следующее свойство получило название алгоритма Евклида. С его помощью можно вычислить наибольший общий делитель двух чисел, а также доказать другие свойства НОД.
Рассмотрев данное свойство, заключаем, что множество общих делителей a и b аналогично множеству делителей НОД этих чисел. Это утверждение, которое является следствием из алгоритма Евклида, позволит нам вычислить все общие делители двух заданных чисел.
Перейдем к другим свойствам.
Докажем данное свойство. Запишем последовательность равенств по алгоритму Евклида:
Это все, что мы хотели бы рассказать о свойствах наибольшего общего делителя.
Наибольший общий делитель (НОД), свойства и формулы
Статья находится на проверке у методистов Skysmart.
Если вы заметили ошибку, сообщите об этом в онлайн-чат
(в правом нижнем углу экрана).
Понятие наибольшего общего делителя
Начнем с самого начала и вспомним, что такое общий делитель. У целого числа может быть несколько делителей. А сейчас нам особенно интересно, как обращаться с делителями сразу нескольких целых чисел.
Делитель натурального числа — это такое натуральное число, которое делит данное число без остатка. Если у натурального числа больше двух делителей, его называют составным.
Если b — делитель целого числа a, которое не равно нулю, то модуль числа b не может быть больше модуля числа a. Значит любое число, не равное 0, имеет конечное число делителей.
Наибольшим общим делителем двух чисел a и b называется наибольшее число, на которое a и b делятся без остатка. Для записи может использоваться аббревиатура НОД. Для двух чисел можно записать вот так: НОД (a, b).
Проверить результаты вычислений можно с помощью онлайн-калькулятора НОД и НОК.
Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.
Взаимно простые числа — это натуральные числа, у которых только один общий делитель — единица. Их НОД равен 1.
Помимо НОД есть еще и НОК, что расшифровывается, как наименьшее общее кратное и означает наименьшее число, которое делится на каждое из исходных чисел без остатка.
Еще один пример. Рассчитаем НОД для 28 и 64.
Д (64) = 2 * 2 * 2 * 2 * 2 * 2
НОД (28; 64) = 2 * 2 = 4
Ответ: НОД (28; 64) = 4
Оформить поиск НОД можно в строчку, как мы сделали выше или в столбик, как на картинке.
Свойства наибольшего общего делителя
У наибольшего общего делителя есть ряд определенных свойств. Опишем их в виде теорем и сразу приведем доказательства.
Важно! Все свойства НОД будем формулировать для положительных целых чисел, при этом будем рассматривать делители только больше нуля.
Свойство 1. Наибольший общий делитель чисел а и b равен наибольшему общему делителю чисел b и а, то есть НОД (a, b) = НОД (b, a). Перемена мест чисел не влияет на конечный результат.
Доказывать свойство не имеет смысла, так как оно напрямую исходит из самого определения НОД.
Свойство 2. Если а делится на b, то множество общих делителей чисел а и b совпадает со множеством делителей числа b, поэтому НОД (a, b) = b.
Доказательство
Любой общий делитель чисел а и b является делителем каждого из этих чисел, в том числе и числа b. Так как а кратно b, то любой делитель числа b является делителем и числа а, благодаря свойствам делимости. Из этого следует, что любой делитель числа b является общим делителем чисел а и b.
Значит, если а делится на b, то совокупность делителей чисел а и b совпадает с совокупностью делителей одного числа b. А так как наибольшим делителем числа b является само число b, то наибольший общий делитель чисела и b также равен b, то есть НОД (а, b) = b.
В частности, если a = b, то НОД (a, b) = НОД (a, a) = НОД (b, b) = a = b.
Доказанное свойство наибольшего делителя можно использовать, чтобы найти НОД двух чисел, когда одно из них делится на другое. При этом НОД равен одному из этих чисел, на которое делится другое число.
Свойство 3. Если a = bq + c, где а, b, с и q — целые числа, то множество общих делителей чисел а и b совпадает со множеством общих делителей чисел b и с. Равенство НОД (a, b) = НОД (b, c) справедливо.
Доказательство
Существует равенство a = bq + c, значит всякий общий делитель чисел а и b делит также и с, исходя из свойств делимости. По этой же причине, всякий общий делитель чисел b и с делит а. Поэтому совокупность общих делителей чисел а и b совпадает с совокупностью общих делителей чисел b и c.
Поэтому должны совпадать и наибольшие из этих общих делителей, и равенство НОД (a, b) = НОД (b, c) можно считать справедливым.
Свойство 4. Если m — любое натуральное число, то НОД (mа, mb) = m * НОД(а, b).
Доказательство
Если умножить на m обе стороны каждого из равенств алгоритма Евклида, то получим, что НОД (mа, mb)= mr, где r — это НОД (а, b). На этом свойстве наибольшего общего делителя основан поиск НОД с помощью разложения на простые множители.
Свойство 5. Пусть р — любой общий делитель чисел а и b, тогда НОД (а : p, b : p) = НОД (а, b) : p. А именно, если p = НОД (a, b) имеем НОД (a : НОД (a, b), b: НОД (a, b)) = 1, то есть, числа a : НОД (a, b) и b : НОД (a, b) — взаимно простые.
Так как a = p(a : p) и b = p(b : p), и в силу предыдущего свойства, мы можем записать цепочку равенств вида НОД (a, b) = НОД (p(a : p), p(b : p)) = p * НОД (a : p, b : p), откуда и следует доказываемое равенство.
Способы нахождения наибольшего общего делителя
Найти наибольший общий делитель можно двумя способами. Рассмотрим оба, чтобы при решении задач выбирать самую оптимальную последовательность действий.
1. Разложение на множители
Чтобы найти НОД нескольких чисел, достаточно разложить их на простые множители и перемножить между собой общие множители для всех чисел.
Пример 1. Найти НОД (84, 90).
Ответ: НОД (84, 90) = 6.
Пример 2. Найти НОД (15, 28).
Ответ: НОД (15, 28) = 1.
Пример 3. Найти НОД для 24 и 18.
Ответ: НОД (24, 18) = 6
2. Алгоритм Евклида
Способ Евклида помогает найти НОД через последовательное деление. Сначала посмотрим, как работает этот способ с двумя числами, а затем применим его к трем и более.
Алгоритм Евклида заключается в следующем: если большее из двух чисел делится на меньшее — наименьшее число и будет их наибольшим общим делителем. Использовать метод Евклида можно легко по формуле нахождения наибольшего общего делителя.
Формула НОД: НОД (a, b) = НОД (b, с), где с — остаток от деления a на b.
Пример 1. Найти НОД для 24 и 8.
Так как 24 делится на 8 и 8 тоже делится на 8, значит, 8 — общий делитель этих чисел. Этот делитель является наибольшим, потому что 8 не может делиться ни на какое число, большее его самого. Поэтому: НОД (24, 8) = 8.
В остальных случаях для нахождения наибольшего общего делителя двух чисел нужно соблюдать такой порядок действий:
Пример 2. Найти наибольший общий делитель чисел 140 и 96:
Последний делитель равен 4 — это значит: НОД (140, 96) = 4.
Ответ: НОД (140, 96) = 4
Пошаговое деление можно записать столбиком:
Чтобы найти наибольший общий делитель трех и более чисел, делаем в такой последовательности:
Знакомство с темой наибольшего общего делителя начинается в 5 классе с теории и закрепляется в 6 классе на практике. В этой статье мы узнали все основные определения, свойства и их доказательства, а также как найти НОД.
Вычисление НОД — ошибка, которой не замечают
Что такое НОД, все знают еще со школы. Для тех, кто подзабыл, напомню: НОД — наибольший общий делитель, делящий два целых числа без остатка. Например, НОД чисел 100 и 45 равен 5, а НОД чисел 17 и 7 равен 1. Существует несколько различных алгоритмов поиска этого числа. Однако, несмотря на то, что это достаточно простые алгоритмы, часто совершают одну маленькую, но очень существенную ошибку.
Алгоритмы вычисления НОД
Естественно, чаще всего пишут первый вариант — он легко запоминается, быстро пишется и достаточно быстро работает.
Претесты
Реализации корректно работают на таких тестах:
Естественно, они будут работать и на подобных тестах, где в качестве аргументов выступают целые неотрицательные числа. Но что, если…
Первые тесты с подвохом
… если заменить одно из чисел нулем? Например так:
Классический алгоритм Евклида (№3) уже попадает в бесконечный цикл.
Копаем глубже
Согласно определению, НОД может быть определен для любых двух целых чисел. Так почему бы не попробовать тесты, где одно из чисел — отрицательное:
Все становится еще интереснее. Первые две реализации выдают в качестве ответа -5. Третий алгоритм снова попадает в бесконечный цикл. Вместе с ним в бесконечном цикле оказывается пятый алгоритм. Четвертый падает по StackOverFlow — скорее всего тоже попадает в бесконечный цикл.
Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель. А таковым является число 5. Ведь и первое, и второе число делятся без остатка на 5. Значит и первые две реализации не дают верный ответ.
Почему решения №№3-5 попадают в бесконечный цикл?
Алгоритм Евклида попадает в цикл из-за бесконечного увеличения аргументов, если один из них отрицательный. Действительно, если посмотреть на эти строки, то можно заметить, что при отрицательном a (или b) операция вычитания заменяется сложением.
Аналогичное происходит в четвертом и пятом алгоритме:
В ситуации, когда a или b равны 0, то происходит бесконечное вычитание нуля, которое никаким образом не меняет значения аргументов.
Так что же не так?
Все эти алгоритмы корректны для входных данных, когда оба числа a и b — целые неотрицательные числа. Но вспомним еще раз — НОД существует для любых двух целых чисел.
Что же делать?
В качестве аргументов в функцию можно передавать абсолютное значение чисел, тогда ответ будет корректен:
Второй способ решения задачи — возвращать абсолютное значение ответа:
Второй вариант гораздо предпочтительнее: будет производиться меньше лишних вычислений, чем в первом варианте.
Итоги
Мы рассмотрели пять различных вариантов вычисления наибольшего общего делителя. Для каждого из них мы указали входные данные, на которых ответ существует, но решение «падает», а также способ решения проблемы.
Такие небольшие ошибки чаще всего допускаются по причине того, что не замечают «скользкие» места решения какой-то задачи. Часть из них отлавливается в процессе тестирования, а часть остается незамеченной.
В ситуации с вычислением НОД почти все реализации приведены с ошибкой. В Сети я нашел лишь парочку корректно работающих решений, остальные идентичны тем, что приведены в начале поста.
Как находить наибольший общий делитель (НОД) двух чисел
Одной из задач, вызывающих проблему у современных школьников, привыкших к месту и не к месту использовать калькуляторы, встроенные в гаджеты, является нахождение наибольшего общего делителя (НОД) двух и более чисел.
Невозможно решить никакую математическую задачу, если неизвестно, о чём собственно спрашивают. Для этого нужно знать, что означает то или иное выражение, используемое в математике.
Общие понятия и определения
Необходимо знать:
В математике приняты следующие записи:
Различные способы найти НОД
Проще всего ответить на вопрос как найти НОД в том случае, когда меньшее число является делителем большего. Оно и будет в подобном случае наибольшим общим делителем.
Например, НОД (15;45) = 15, НОД (48;24) = 24.
Но такие случаи в математике являются весьма редкими, поэтому для того, чтобы находить НОД используются более сложные приёмы, хотя проверять этот вариант перед началом работы все же весьма рекомендуется.
Способ разложения на простые сомножители
Если необходимо найти НОД двух или более различных чисел, достаточно разложить каждое из них на простые сомножители, а затем произвести процесс умножения тех из них, которые имеются в каждом из чисел.
Пример 1
Рассмотрим, как находить НОД 36 и 90:
НОД (36;90) = 1*2*3*3 = 18.
Теперь посмотрим как находить то же самое в случае трёх чисел, возьмём для примера 54; 162; 42.
Как разложить 36 мы уже знаем, разберёмся с остальными:
Таким образом, НОД (36;162;42) = 1*2*3 = 6.
Следует заметить, что единицу в разложении писать совершенно необязательно.
Рассмотрим способ, как просто раскладывать на простые множители, для этого слева запишем необходимую нам цифру, а справа станем писать простые делители.
Разделять колонки можно, как знаком деления, так и простой вертикальной чертой.
Евклидов способ
Этот вариант известен человечеству ещё со времён древнегреческой цивилизации, он во многом проще, и приписывается великому математику Евклиду, хотя весьма похожие алгоритмы применялись и ранее. Этот способ заключается в использовании следующего алгоритма, мы делим большее число с остатком на меньшее. Затем наш делитель делим на остаток и продолжаем так действовать по кругу пока не произойдёт деление нацело. Последнее значение и окажется искомым наибольшим общим делителем.
Приведём пример использования данного алгоритма:
попробуем выяснить какой НОД у 816 и 252:
Итак, по завершении нашего процесса мы получили НОД (816;252) = 12.
Действия при необходимости определения НОД если задано более двух значений
Мы уже разобрались, что делать в случае, когда имеется два различных числа, теперь научимся действовать, если их имеется 3 и более.
При всей кажущейся сложности, данная задача проблем у нас уже не вызовет. Сейчас мы выбираем два любые числа и определяем искомое для них значение. Следующим шагом отыскиваем НОД у полученного результата и третьего из заданных значений. Затем снова действуем по уже известному нам принципу для четвёртого пятого и так далее.
Заключение
Итак, при кажущейся большой сложности поставленной перед нами изначально задачи, на самом деле все просто, главное уметь выполнять безошибочно процесс делений и придерживаться любого из двух описанных выше алгоритмов.
Видео
С помощью видео вы сможете узнать, как найти наибольший общий делитель.