Одной из задач, вызывающих проблему у современных школьников, привыкших к месту и не к месту использовать калькуляторы, встроенные в гаджеты, является нахождение наибольшего общего делителя (НОД) двух и более чисел.
Невозможно решить никакую математическую задачу, если неизвестно, о чём собственно спрашивают. Для этого нужно знать, что означает то или иное выражение , используемое в математике.
Общие понятия и определения
Необходимо знать:
- Если некое число можно использовать для подсчёта различных предметов, например, девять столбов, шестнадцать домов, то оно является натуральным. Самым маленьким из них будет единица.
- Когда натуральное число делится на другое натуральное число, то говорят, что меньшее число - это делитель большего.
- Если два и более различных числа делятся на некое число без остатка, то говорят, что последнее будет их общим делителем (ОД).
- Самый большой из ОД именуется наибольшим общим делителем (НОД).
- В таком случае, когда у числа есть только два натуральных делителя (оно само и единичка), оно называется простым. Самое маленькое среди них - двойка, к тому же она и единственное чётное в их ряду.
- В случае если у двух чисел максимальным общим делителем является единица, то они будут взаимно простыми.
- Число, у которого больше чем два делителя, именуется составным.
- Процесс когда находятся все простые множители, которые при умножении между собой дадут в произведении начальное значение в математике называют разложением на простые множители. Причём одинаковые множители в разложении могут встречаться неоднократно.
В математике приняты следующие записи:
- Делители Д (45) = (1;3;5;9;45).
- ОД (8;18) = (1;2).
- НОД (8;18) = 2.
Различные способы найти НОД
Проще всего ответить на вопрос как найти НОД в том случае, когда меньшее число является делителем большего. Оно и будет в подобном случае наибольшим общим делителем.
Например, НОД (15;45) = 15, НОД (48;24) = 24.
Но такие случаи в математике являются весьма редкими, поэтому для того, чтобы находить НОД используются более сложные приёмы, хотя проверять этот вариант перед началом работы все же весьма рекомендуется.
Способ разложения на простые сомножители
Если необходимо найти НОД двух или более различных чисел , достаточно разложить каждое из них на простые сомножители, а затем произвести процесс умножения тех из них, которые имеются в каждом из чисел.
Пример 1
Рассмотрим, как находить НОД 36 и 90:
- 36 = 1*2*2*3*3;
- 90 = 1*2*3*3*5;
НОД (36;90) = 1*2*3*3 = 18.
Теперь посмотрим как находить то же самое в случае трёх чисел , возьмём для примера 54; 162; 42.
Как разложить 36 мы уже знаем, разберёмся с остальными:
- 162 = 1*2*3*3*3*3;
- 42 = 1*2*3*7;
Таким образом, НОД (36;162;42) = 1*2*3 = 6.
Следует заметить, что единицу в разложении писать совершенно необязательно.
Рассмотрим способ, как просто раскладывать на простые множители , для этого слева запишем необходимую нам цифру, а справа станем писать простые делители.
Разделять колонки можно, как знаком деления, так и простой вертикальной чертой.
- 36 / 2 продолжим наш процесс деления;
- 18 / 2 далее;
- 9 / 3 и ещё раз;
- 3 / 3 сейчас совсем элементарно;
- 1 - результат готов.
Искомое 36 = 2*2*3*3.
Евклидов способ
Этот вариант известен человечеству ещё со времён древнегреческой цивилизации, он во многом проще, и приписывается великому математику Евклиду, хотя весьма похожие алгоритмы применялись и ранее. Этот способ заключается в использовании следующего алгоритма , мы делим большее число с остатком на меньшее. Затем наш делитель делим на остаток и продолжаем так действовать по кругу пока не произойдёт деление нацело. Последнее значение и окажется искомым наибольшим общим делителем.
Приведём пример использования данного алгоритма :
попробуем выяснить какой НОД у 816 и 252:
- 816 / 252 = 3 и остаток 60. Сейчас 252 разделим на 60;
- 252 / 60 = 4 в остатке на этот раз окажется 12. Продолжим наш круговой процесс, разделим шестьдесят на двенадцать;
- 60 / 12 = 5. Поскольку на сей раз никакого остатка мы не получили, то у нас готов результат, двенадцать будет искомым для нас значением.
Итак, по завершении нашего процесса мы получили НОД (816;252) = 12.
Действия при необходимости определения НОД если задано более двух значений
Мы уже разобрались, что делать в случае, когда имеется два различных числа, теперь научимся действовать, если их имеется 3 и более .
При всей кажущейся сложности, данная задача проблем у нас уже не вызовет. Сейчас мы выбираем два любые числа и определяем искомое для них значение. Следующим шагом отыскиваем НОД у полученного результата и третьего из заданных значений. Затем снова действуем по уже известному нам принципу для четвёртого пятого и так далее.
Заключение
Итак, при кажущейся большой сложности поставленной перед нами изначально задачи, на самом деле все просто, главное уметь выполнять безошибочно процесс делений и придерживаться любого из двух описанных выше алгоритмов.
Хотя оба способа и являются вполне приемлемыми, в общеобразовательной школе гораздо чаще применяется первый способ . Это связано с тем, что разложение на простые множители понадобится при изучении следующей учебной темы - определение наибольшего общего кратного (НОК). Но все же стоит ещё раз заметить - применение алгоритма Евклида ни в коей мере не может считаться ошибочным.
Видео
С помощью видео вы сможете узнать, как найти наибольший общий делитель.
Чтобы найти наименьшее общее кратное (НОК) и наибольший общий делитель (НОД) двух чисел воспользуйтесь нашим онлайн калькулятором:
Введите числа: и
НОК:
НОД:
Определить
Просто введите числа и получите результат.
Как найти НОК двух чисел
Наименьшее общее кратное (НОК) двух или нескольких чисел – это самое маленькое число, которое можно разделить на каждое из этих чисел без остатка.
Для того чтобы найти наименьшее общее кратное (НОК) двух чисел можно воспользоваться следующим алгоритмом (5 класс):
- Оба числа (сначала наибольшее число).
- Сравним множители большего числа с множителями меньшего. Выделим все множители меньшего числа, которых нет у большего.
- Добавим выделенные множители меньшего числа к множителям большего.
- Найдём НОК, перемножив ряд множителей, полученных в пункте 3.
Пример
Для примера определим НОК чисел 8 и 22 .
1) Раскладываем на простые множители:
2) Выделим все множители 8-ми, которых нет у 22-х:
8 = 2⋅2 ⋅2
3) Добавим выделенные множители 8-ми к множителям 22-х:
НОК (8; 22) = 2 · 11 · 2 · 2
4) Вычисляем НОК:
НОК (8; 22) = 2 · 11 · 2 · 2 = 88
Как найти НОД двух чисел
Наибольший общий делитель (НОД) двух или нескольких чисел – это наибольшее натуральное целое число, на которое эти числа можно разделить без остатка.
Чтобы найти наибольший общий делитель (НОД) двух чисел, для начала необходимо разложить их на простые множители. Затем нужно выделить общие множители, которые имеются и у первого числа и у второго. Перемножаем их – это и будет НОД. Чтобы лучше понять алгоритм рассмотрим пример:
Пример
Для примера определим НОД чисел 20 и 30 .
20 = 2 ⋅2⋅5
30 = 2 ⋅3⋅5
НОД(20,30) = 2⋅5 = 10
Решим задачу. У нас есть два типа печенья. Одни шоколадные, а другие простые. Шоколадных 48 штук, а простых 36. Необходимо составить из этого печенья максимально возможное число подарков, при этом надо использовать их все.
Для начала выпишем все делители каждого из этих двух чисел, так как оба эти числа должны делиться на количество подарков.
Получаем,
- 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
- 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
Найдем среди делителей общие, которые есть как у первого, так и у второго числа.
Общими делителями будут: 1, 2, 3, 4, 6, 12.
Наибольшим из всех общих делителей является число 12. Это число называют наибольшим общим делителем чисел 36 и 48.
Исходя из полученного результата, можем заключить, что из всего печенья можно составить 12 подарков. В одном таком подарке будет 4 шоколадных печенья и 3 обычных печенья.
Определение наибольшего общего делителя
- Наибольшее натуральное число, на которое делятся без остатка два числа a и b, называют наибольшим общим делителем этих чисел.
Иногда для сокращения записи используют аббревиатуру НОД.
Некоторые пары чисел имеют в качестве наибольшего общего делителя единицу. Такие числа называют взаимно простыми числами. Например, числа 24 и 35. Имеют НОД =1.
Как найти наибольший общий делитель
Для того чтобы найти наибольший общий делитель не обязательно выписывать все делители данных чисел.
Можно поступить иначе. Сначала разложить на простые множители оба числа.
- 48 = 2*2*2*2*3,
- 36 = 2*2*3*3.
Теперь из множителей, которые входят в разложение первого числа, вычеркнем все те, которые не входят в разложение второго числа. В нашем случае это две двойки.
- 48 = 2*2*2*2*3 ,
- 36 = 2*2*3 *3.
Останутся множители 2, 2 и 3. Их произведение равно 12. Это число и будет являться наибольшим общим делителем чисел 48 и 36.
Это правило можно распространить на случай с тремя, четырьмя и т.д. числами.
Общая схема нахождения наибольшего общего делителя
- 1. Разложить числа на простые множители.
- 2. Из множителей, входящих в разложение одного из этих чисел, вычеркнуть те, которые не входят в разложение других чисел.
- 3. Посчитать произведение оставшихся множителей.
Чтобы понять, как вычислять НОК, следует определиться в первую очередь со значением термина "кратное".
Кратным числу А называют такое натуральное число, которое без остатка делится на А. Так, числами кратными 5 можно считать 15, 20, 25 и так далее.
Делителей конкретного числа может быть ограниченное количество, а вот кратных бесконечное множество.
Общее кратное натуральных чисел - число, которое делится на них без остатка.
Как найти наименьшее общее кратное чисел
Наименьшее общее кратное (НОК) чисел (двух, трех или больше) - это самое маленькое натурально число, которое делится на все эти числа нацело.
Чтобы найти НОК, можно использовать несколько способов.
Для небольших чисел удобно выписать в строчку все кратные этих чисел до тех пор, пока среди них не найдется общее. Кратные обозначают в записи заглавной буквой К.
Например, кратные числа 4 можно записать так:
К (4) = {8,12, 16, 20, 24, ...}
К (6) = {12, 18, 24, ...}
Так, можно увидеть, что наименьшим общим кратным чисел 4 и 6 является число 24. Эту запись выполняют следующим образом:
НОК (4, 6) = 24
Если числа большие, найти общее кратное трех и более чисел, то лучше использовать другой способ вычисления НОК.
Для выполнения задания необходимо разложить предложенные числа на простые множители.
Сначала нужно выписать в строчку разложение наибольшего из чисел, а под ним - остальных.
В разложении каждого числа может присутствовать различное количество множителей.
Например, разложим на простые множители числа 50 и 20.
В разложении меньшего числа следует подчеркнуть множители, которые отсутствуют в разложении первого самого большого числа, а затем их добавить к нему. В представленном примере не хватает двойки.
Теперь можно вычислить наименьшее общее кратное 20 и 50.
НОК (20, 50) = 2 * 5 * 5 * 2 = 100
Так, произведение простых множителей большего числа и множителей второго числа, которые не вошли в разложение большего, будет наименьшим общим кратным.
Чтобы найти НОК трех чисел и более, следует их все разложить на простые множители, как и в предыдущем случае.
В качестве примера можно найти наименьшее общее кратное чисел 16, 24, 36.
36 = 2 * 2 * 3 * 3
24 = 2 * 2 * 2 * 3
16 = 2 * 2 * 2 * 2
Так, в разложение большего числа на множители не вошли только две двойки из разложения шестнадцати (одна есть в разложении двадцати четырех).
Таким образом, их нужно добавить к разложению большего числа.
НОК (12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9
Существуют частные случаи определения наименьшего общего кратного. Так, если одно из чисел можно поделить без остатка на другое, то большее из этих чисел и будет наименьшим общим кратным.
Например, НОК двенадцати и двадцати четырех будет двадцать четыре.
Если необходимо найти наименьшее общее кратное взаимно простых чисел, не имеющих одинаковых делителей, то их НОК будет равняться их произведению.
Например, НОК (10, 11) = 110.
Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.
Например :
Число 12 делится на 1, на 2, на 3, на 4, на 6, на 12;
Число 36 делится на 1, на 2, на 3, на 4, на 6, на 12, на 18, на 36.
Числа, на которые число делится нацело (для 12 это 1, 2, 3, 4, 6 и 12) называются делителями числа . Делитель натурального числа a - это такое натуральное число, которое делит данное число a без остатка. Натуральное число, которое имеет более двух делителей, называется составным . Обратите внимание, что числа 12 и 36 имеют общие делители. Это числа: 1, 2, 3, 4, 6, 12. Наибольший из делителей этих чисел - 12.
Общий делитель двух данных чисел a и b - это число, на которое делятся без остатка оба данных числа a и b . Общий делитель нескольких чисел (НОД) — это число, служащее делителем для каждого из них.
Кратко наибольший общий делитель чисел a и b записывают так:
Пример : НОД (12; 36) = 12.
Делители чисел в записи решения обозначают большой буквой «Д».
Пример:
НОД (7; 9) = 1
Числа 7 и 9 имеют только один общий делитель - число 1. Такие числа называют взаимно простыми чи слами .
Взаимно простые числа - это натуральные числа, которые имеют только один общий делитель - число 1. Их НОД равен 1.
Наибольший общий делитель (НОД), свойства.
- Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример : для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
- Следствие 1: множество общих делителей m и n совпадает с множеством делителей НОД(m , n ).
- Следствие 2: множество общих кратных m и n совпадает с множеством кратных НОК (m , n ).
Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
- Наибольший общий делитель чисел m и n может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:
и поэтому представим в виде линейной комбинации чисел m и n :
Это соотношение называется соотношением Безу , а коэффициенты u и v — коэффициентами Безу . Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД (a 1 , a 2 , … , a n ).
Вычисление наибольшего общего делителя (НОД).
Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм . Кроме того, значение НОД (m ,n ) можно легко вычислить, если известно каноническое разложение чисел m и n на простые множители:
где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД (m ,n ) и НОК (m ,n ) выражаются формулами:
Если чисел более двух: , их НОД находится по следующему алгоритму:
— это и есть искомый НОД.
Также, для того, чтобы найти наибольший общий делитель , можно разложить каждое из заданных чисел на простые множители . Потом выписать отдельно только те множители, которые входят во все заданные числа. Потом перемножаем между собой выписанные числа - результат перемножения и есть наибольший общий делитель.
Разберем пошагово вычисление наибольшего общего делителя:
1. Разложить делители чисел на простые множители:
Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое, справа - делитель. Далее в левом столбце записываем значения частных. Поясним сразу на примере. Разложим на простые множители числа 28 и 64.
2. Подчёркиваем одинаковые простые множители в обоих числах:
28 = 2 . 2 . 7
64 = 2 . 2 . 2 . 2 . 2 . 2
3. Находим произведение одинаковых простых множителей и записываем ответ:
НОД (28; 64) = 2 . 2 = 4
Ответ: НОД (28; 64) = 4
Оформить нахождение НОД можно двумя способами: в столбик (как делали выше) или «в строчку».
Первый способ записи НОД:
Найти НОД 48 и 36.
НОД (48; 36) = 2 . 2 . 3 = 12
Второй способ записи НОД:
Теперь запишем решение поиска НОД в строчку. Найти НОД 10 и 15.
Д (10) = {1, 2, 5, 10}
Д (15) = {1, 3, 5, 15}
Д (10, 15) = {1, 5}
Loading...