Что такое наибольший делитель числа
Наибольший общий делитель (НОД): определение, примеры и свойства
Что такое общие делители
Чтобы понять, что из себя представляет наибольший общий делитель, сначала сформулируем, что вообще такое общий делитель для целых чисел.
В статье о кратных и делителях мы говорили, что у целого числа всегда есть несколько делителей. Здесь же нас интересуют делители сразу некоторого количества целых чисел, особенно общие (одинаковые) для всех. Запишем основное определение.
Общим делителем нескольких целых чисел будет такое число, которое может быть делителем каждого числа из указанного множества.
Зная свойства делимости, мы можем утверждать, что любое целое число можно разделить на единицу и минус единицу, значит, у любого набора целых чисел уже будет как минимум два общих делителя.
Что такое наибольший общий делитель (НОД)
Переходим к формулировке основного определения.
Наибольшим общим делителем нескольких чисел является самое большое целое число, которое делит все эти числа.
Для трех и более чисел определение наибольшего общего делителя будет почти таким же.
Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.
Проверить правильность данного утверждения можно с помощью записи всех делителей этих чисел и последующего выбора наибольшего из них.
На практике часто встречаются случаи, когда наибольший общий делитель равен одному из чисел. Это происходит тогда, когда на данное число можно разделить все остальные числа (в первом пункте статьи мы привели доказательство этого утверждения).
Основные свойства НОД и алгоритм Евклида
У наибольшего общего делителя есть некоторые характерные свойства. Сформулируем их в виде теорем и докажем каждое из них.
Отметим, что данные свойства сформулированы для целых чисел больше нуля, а делители мы рассмотрим только положительные.
Данное свойство следует из самого определения НОД и не нуждается в доказательствах.
Докажем это утверждение.
Следующее свойство получило название алгоритма Евклида. С его помощью можно вычислить наибольший общий делитель двух чисел, а также доказать другие свойства НОД.
Рассмотрев данное свойство, заключаем, что множество общих делителей 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 классе на практике. В этой статье мы узнали все основные определения, свойства и их доказательства, а также как найти НОД.
Как находить наибольший общий делитель (НОД) двух чисел
Одной из задач, вызывающих проблему у современных школьников, привыкших к месту и не к месту использовать калькуляторы, встроенные в гаджеты, является нахождение наибольшего общего делителя (НОД) двух и более чисел.
Невозможно решить никакую математическую задачу, если неизвестно, о чём собственно спрашивают. Для этого нужно знать, что означает то или иное выражение, используемое в математике.
Общие понятия и определения
Необходимо знать:
В математике приняты следующие записи:
Различные способы найти НОД
Проще всего ответить на вопрос как найти НОД в том случае, когда меньшее число является делителем большего. Оно и будет в подобном случае наибольшим общим делителем.
Например, НОД (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 и более.
При всей кажущейся сложности, данная задача проблем у нас уже не вызовет. Сейчас мы выбираем два любые числа и определяем искомое для них значение. Следующим шагом отыскиваем НОД у полученного результата и третьего из заданных значений. Затем снова действуем по уже известному нам принципу для четвёртого пятого и так далее.
Заключение
Итак, при кажущейся большой сложности поставленной перед нами изначально задачи, на самом деле все просто, главное уметь выполнять безошибочно процесс делений и придерживаться любого из двух описанных выше алгоритмов.
Видео
С помощью видео вы сможете узнать, как найти наибольший общий делитель.
Делители и кратные
В данном уроке мы рассмотрим такие понятия как делители и кратные.
Что такое делитель?
Мы знаем, что делитель это число, показывающее на сколько частей нужно разделить делимое. Например, в выражении 8 : 2 = 4, делителем является число 2. Это число показывает на сколько частей нужно разделить число 8. После разделения получается ответ 4. Как видно из примера, число 8 делится на число 2 без остатка. Говорят, что число 2 является делителем числа 8.
Пример 1. Число 2 является делителем числа 8, поскольку 8 делится на 2 без остатка:
Пример 2. Число 3 является делителем числа 9, поскольку 9 делится на 3 без остатка:
Пример 3. Число 4 не является делителем числа 10 поскольку 10 не делится на 4 без остатка:
10 : 4 = 2 (2 в остатке)
Определение. Делителем числа а называется число, на которое число а делится без остатка.
Делителем числа 12 называется число, на которое 12 делится без остатка.
Попробуем перечислить эти числа:
Все эти числа являются делителями числа 12, поскольку число 12 делится на них без остатка. Покажем это:
12 : 1 = 12
12 : 2 = 6
12 : 3 = 4
12 : 4 = 3
12 : 6 = 2
12 : 12 = 1
Кратные числа
Если какое-нибудь число без остатка разделилось на другое, то его называют кратным этого числа. Например, 6 без остатка делится на 3. Поэтому 6 является кратным числа 3
Определение. Кратным числа а называется число, которое делится без остатка на а.
Кратным числа 5 называется число, которое делится без остатка на 5 .
У любого числа бесконечно много кратных. Например, первыми кратными числа 5, являются числа 5, 10, 15, 20, 25. Все они кратны 5, поскольку делятся на 5 без остатка:
5 : 5 = 1
10 : 5 = 2
15 : 5 = 3
20 : 5 = 4
25 : 5 = 5
Признаки делимости чисел
Признаки делимости чисел используются для того, чтобы ускорить процесс деления чисел. Существует множество признаков делимости и других интересных алгоритмов, значительно ускоряющих решение и освобождающих от излишней волокиты. Рассмотрим наиболее популярные из них.
Признак делимости на 10
Любое число, которое оканчивается нулем, делится без остатка на 10. Чтобы получить частное, достаточно отбросить цифру 0 в делимом.
Например, 380 : 10 = 38. Мы просто отбросили последний ноль в числе 380.
В случае, если мы имеем выражение такого вида 385 : 10, то получится 38 и 5 в остатке, поскольку 380 : 10 = 38, а пятерка это остаток, который не разделился.
Таким образом, если число оканчивается цифрой 0, то оно делится без остатка на 10. Если же оно оканчивается другой цифрой, то оно не делится без остатка на 10. Остаток в этом случае равен последней цифре числа. Действительно, в примере 385 : 10 = 38 (5 в остатке), остаток равен последней цифре в числе 385, то есть пятерке.
Признак делимости на 5 и на 2
Любое число, которое оканчивается нулем, делится без остатка и на 5, и на 2.
Признак делимости на 5
Если число оканчивается цифрой 0 или 5, то оно делится без остатка на 5.
Признак делимости на 3
Число делится на 3, если сумма цифр этого числа делится на 3. Например, рассмотрим число 27, сумма его цифр 2 + 7 = 9. Девять, как мы знаем делится на 3, значит и 27 делится на 3:
Признак делимости на 9
Число делится на 9, если сумма его цифр делится на 9. Например, рассмотрим число 18. Сумма его цифр 1 + 8 = 9. Девять делится на девять, значит и 18 делится на 9
Рассмотрим число 846. Сумма его цифр 8 + 4 + 6 = 18. Восемнадцать делится на девять, значит и 846 делится на 9:
Чётные и нечётные числа
Чётным называется число, которое делится без остатка на 2. Например, число 20 является четным, поскольку оно делится без остатка на 2:
Нечётным называется число, если при его делении на 2, остаётся остаток 1. Например число 21 является нечетным, поскольку после его деления на 2 остается остаток 1:
21 : 2 = 10 (1 в остатке)
Как распознать чётное число от нечетного, не выполняя деления на 2? Очень просто. Из однозначных чисел чётными являются числа 0, 2, 4, 6, 8, а нечетными являются 1, 3, 5, 7, 9. Если число оканчивается чётной цифрой, то это число является чётным. Если число оканчивается нечетной цифрой, то это число является нечетным.
Например, число 308 чётно, поскольку оно оканчивается чётной цифрой. Число 1024 тоже четно, поскольку оканчивается четной цифрой.
А числа 305 и 1027 являются нечётными, поскольку они оканчиваются нечётными цифрами.
Простые и составные числа
Простым называется число, которое делится без остатка на единицу и на само себя. Другими словами, имеет только два делителя. Например, число 5 делится без остатка на единицу и на само себя:
Значит, число 5 является простым числом.
Составным же называется число, которое имеет два и более делителя. Например, число 4 составное, поскольку у него два и более делителя: 4, 2 и 1
Значит, число 4 является составным числом.
Разложение составного числа на простые множители
Любое составное число можно разложить на простые множители. Чем-то похожим мы занимались в уроке замены в выражениях. Из этого урока мы узнали, что любое число, входящее в выражение, можно заменить на то же самое, но записанное в другом виде.
Суть разложения числа на простые множители заключается в том, чтобы представить это число в виде произведения нескольких простых множителей.
Разложим число 4 на простые множители. Для этого соберем данное число из других чисел, при этом соединим их знаком умножения (×). Число 4 состоит из чисел 2 и 2. Эти два числа и являются простыми множителями, из которых состоит число 4
Разложим на множители число 6. Число 6 можно собрать из чисел 2 и 3. Эти два числа и являются простыми множителями, из которых состоит число 6
Большие числа раскладываются таким же образом. Сначала их раскладывают на большие множители, затем эти большие множители раскладывают на маленькие. И так до тех пор, пока каждый множитель не станет простым числом.
Например, разложим число 180 на простые множители. Число 180 это два множителя 18 и 10
Теперь раскладываем множители 18 и 10 на другие множители:
Теперь раскладываем выделенную синюю шестерку. Это последний большой множитель, который можно разложить на простые множители:
Теперь собираем все простые множители вместе:
На множители можно разложить только составное число. Простое число на множители не раскладывается. Именно поэтому, когда разложение доходит до простых чисел, мы эти простые числа дальше не раскладываем.
Есть и второй способ разложения на простые множители. Он проще и хорошо подходит для больших чисел. Суть этого способа заключается в том, что сначала проводится вертикальная линия. Затем слева от этой линии записываются делимые, а справа — делители, которые впоследствии собирают во множители.
При разложении числа этим способом, используют признаки делимости, такие как: признаки делимости на 2, на 3, на 5 и другие.
Например, разложим предыдущее число 180 этим способом.
Проводим вертикальную линию и слева записываем первое делимое 180
Теперь применяем признаки делимости. В первую очередь проверяем делится ли 180 на 2. Если делится, то нужно записать эту двойку справа от вертикальной линии.
180 делится на 2, поскольку 180 оканчивается нулём. Записываем двойку справа от вертикальной линии:
Теперь делим 180 на 2 и получаем второе делимое 90. Записываем это делимое слева от вертикальной линии:
Теперь делим 90. Снова применяем признаки делимости. Проверяем делится ли 90 на 2.
90 делится на 2, поскольку 90 оканчивается нулём. Записываем двойку справа от вертикальной линии:
Теперь делим 90 на 2, получаем третье делимое 45. Записываем это делимое слева от вертикальной линии:
Теперь делим 45. Снова применяем признаки делимости. Проверяем делится ли 45 на 2.
45 на 2 не делится. Тогда проверяем делится ли 45 на 3.
45 делится на 3, поскольку сумма цифр 4 и 5 делится на 3. Записываем тройку справа от вертикальной линии:
Делим 45 на 3, получаем четвёртое делимое 15. Записываем это делимое слева от вертикальной линии:
Теперь делим 15. Проверяем делится ли 15 на 2.
15 не делится на 2. Тогда проверяем делится ли 15 на 3.
15 на 3 делится, поскольку сумма цифр 1 и 5 делится на 3. Записываем тройку справа от вертикальной линии:
Делим 15 на 3, получаем пятое делимое 5. Записываем пятёрку слева от вертикальной линии:
Теперь делим 5. Проверяем делится ли 5 на 2.
5 не делится на 2. Тогда проверяем делится ли 5 на 3.
5 не делится на 3. Тогда проверяем делится ли 5 на 5.
5 делится на 5. Записываем эту пятёрку справа от вертикальной линии:
Делим 5 на 5, получаем шестое делимое 1. Записываем эту единицу слева от вертикальной линии:
На этом деление завершается, поскольку мы достигли единицы. Делители, которые записывают справа от вертикальной линии должны быть простыми числами. Поэтому, когда делимое 5 не разделилось на 2, а затем не разделилось на 3, мы попробовали разделить его на 5, не пробуя разделить на 4, поскольку 4 является не простым, а составным числом.
Теперь переписываем в один ряд все делители, которые записаны справа от вертикальной линии. Они и будут разложением числа 180 на простые множители. Желательно записывать их, начиная с самых малых. Это позволяет упорядочить их по возрастанию:
Не расстраивайтесь, если будете испытывать затруднения при разложении чисел на простые множители. Эта тема требует немного практики. Для тренировки можете разложить на простые множители следующие числа: 256, 378, 512.
Нахождение делителей числа
В начале данного урока было сказано, что делителем называется число, на которое другое число делится без остатка.
Например, число 2 является делителем числа 6, поскольку число 6 можно без остатка разделить на 2
6 : 2 = 3
Ещё делителем числа 6 является число 3
6 : 3 = 2
Ещё делителем числа 6 является число 1
6 : 1 = 6
Наконец, делителем числа 6 является само это число
6 : 6 = 1
Перечислим все делители числа 6
1, 2, 3, 6
Иногда возникает необходимость найти все делители какого-нибудь числа. Чтобы понять, как это делается, рассмотрим несколько примеров.
Пример 1. Найти делители числа 12
Во-первых, единица является делителем любого числа. Пусть и у нас первым делителем числа 12 будет 1
Теперь раскладываем число 12 на простые множители:
Получили разложение 2 × 2 × 3.
В процессе разложения числа 12 на простые множители, мы делили его на числа 2 и 3. На них число 12 разделилось без остатка, значит они тоже являются делителями числа 12. Внесём эти два числа в нашу таблицу делителей:
Чтобы получить остальные делители числа 12, нужно найти все возможные произведения его простых множителей между собой. Получаемые в результате ответы и будут остальными делителями числа 12.
Число 12 мы разложили на простые множители 2 × 2 × 3. Найдём все возможные произведения этих простых множителей между собой. Первое произведение это 2 × 2. Это произведение равно 4
Занесём число 4 в нашу таблицу делителей
Следующее возможное произведение из простых множителей числа 12 это произведение 2 × 3. Данное произведение равно 6. Занесём число 6 в нашу таблицу делителей:
Последнее возможное произведение из простых множителей числа 12 это произведение из всех его множителей, а именно 2 × 2 × 3. Это произведение равно 12. Занесём число 12 в нашу таблицу делителей:
Таким образом, делителями числа 12 являются числа 1, 2, 3, 4, 6, 12.
На основании приведённого примера можно сформировать правило для нахождения делителей числа:
Чтобы найти делители числа, нужно:
Пример 2. Найти делители числа 6
Первым делителем числа 6 запишем единицу:
Теперь разложим число 6 на простые множители:
Выпишем из полученного разложения те множители, которые являются делителями числа 6. Видим, что это множители 2 и 3. Они будут следующими делителями числа 6. Допишем их к нашим делителям:
1, 2, 3
1, 2, 3, 6