Как найти неизвестный общий делитель

Как найти НОД

• Нахождение путём разложения на множители
• Алгоритм Евклида

Рассмотрим два способа нахождения наибольшего общего делителя.

Нахождение путём разложения на множители

Первый способ заключается в нахождении наибольшего общего делителя путём разложения данных чисел на простые множители.

Чтобы найти НОД нескольких чисел, достаточно, разложить их на простые множители и перемножить между собой те из них, которые являются общими для всех данных чисел.

Алгоритм Евклида

Второй способ (иначе его называют способом Евклида) заключается в нахождении НОД путём последовательного деления.

Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.

Если большее из двух данных чисел делится на меньшее, то число, которое меньше и будет их наибольшим общим делителем.

В остальных случаях, чтобы найти наибольший общий делитель двух чисел используется следующий порядок действий:

1. Из двух данных чисел большее число делят на меньшее.
2. Затем, меньшее число делят на остаток, получившийся от деления большего числа на меньшее.
3. Далее, первый остаток делят на второй остаток, который получился от деления меньшего числа на первый остаток.
4. Второй остаток делят на третий, который получился от деления первого остатка на второй и т. д.
5. Таким образом деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель как раз и будет наибольшим общим делителем.

Чтобы найти наибольший общий делитель трёх и более данных чисел, используем следующий порядок действий:

1. Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
2. Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
3. Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.

Одной из задач, вызывающих проблему у современных школьников, привыкших к месту и не к месту использовать калькуляторы, встроенные в гаджеты, является нахождение наибольшего общего делителя (НОД) двух и более чисел.

Невозможно решить никакую математическую задачу, если неизвестно, о чём собственно спрашивают. Для этого нужно знать, что означает то или иное выражение, используемое в математике.

Общие понятия и определения

Необходимо знать:

1. Если некое число можно использовать для подсчёта различных предметов, например, девять столбов, шестнадцать домов, то оно является натуральным. Самым маленьким из них будет единица.
2. Когда натуральное число делится на другое натуральное число, то говорят, что меньшее число — это делитель большего.
3. Если два и более различных числа делятся на некое число без остатка, то говорят, что последнее будет их общим делителем (ОД).
4. Самый большой из ОД именуется наибольшим общим делителем (НОД).
5. В таком случае, когда у числа есть только два натуральных делителя (оно само и единичка), оно называется простым. Самое маленькое среди них — двойка, к тому же она и единственное чётное в их ряду.
6. В случае если у двух чисел максимальным общим делителем является единица, то они будут взаимно простыми.
7. Число, у которого больше чем два делителя, именуется составным.
8. Процесс когда находятся все простые множители, которые при умножении между собой дадут в произведении начальное значение в математике называют разложением на простые множители. Причём одинаковые множители в разложении могут встречаться неоднократно.

В математике приняты следующие записи:

1. Делители Д (45) = (1;3;5;9;45).
2. ОД (8;18) = (1;2).
3. НОД (8;18) = 2.

Различные способы найти НОД

Проще всего ответить на вопрос как найти НОД в том случае, когда меньшее число является делителем большего. Оно и будет в подобном случае наибольшим общим делителем.

Например, НОД (15;45) = 15, НОД (48;24) = 24.

Но такие случаи в математике являются весьма редкими, поэтому для того, чтобы находить НОД используются более сложные приёмы, хотя проверять этот вариант перед началом работы все же весьма рекомендуется.

Способ разложения на простые сомножители

Если необходимо найти НОД двух или более различных чисел, достаточно разложить каждое из них на простые сомножители, а затем произвести процесс умножения тех из них, которые имеются в каждом из чисел.

Пример 1

Рассмотрим, как находить НОД 36 и 90:

1. 36 = 1*2*2*3*3;
2. 90 = 1*2*3*3*5;

НОД (36;90) = 1*2*3*3 = 18.

Теперь посмотрим как находить то же самое в случае трёх чисел, возьмём для примера 54; 162; 42.

Как разложить 36 мы уже знаем, разберёмся с остальными:

1. 162 = 1*2*3*3*3*3;
2. 42 = 1*2*3*7;

Таким образом, НОД (36;162;42) = 1*2*3 = 6.

Следует заметить, что единицу в разложении писать совершенно необязательно.

Рассмотрим способ, как просто раскладывать на простые множители, для этого слева запишем необходимую нам цифру, а справа станем писать простые делители.

Разделять колонки можно, как знаком деления, так и простой вертикальной чертой.

1. 36 / 2 продолжим наш процесс деления;
2. 18 / 2 далее;
3. 9 / 3 и ещё раз;
4. 3 / 3 сейчас совсем элементарно;
5. 1 — результат готов.

Искомое 36 = 2*2*3*3.

Евклидов способ

Этот вариант известен человечеству ещё со времён древнегреческой цивилизации, он во многом проще, и приписывается великому математику Евклиду, хотя весьма похожие алгоритмы применялись и ранее. Этот способ заключается в использовании следующего алгоритма, мы делим большее число с остатком на меньшее. Затем наш делитель делим на остаток и продолжаем так действовать по кругу пока не произойдёт деление нацело. Последнее значение и окажется искомым наибольшим общим делителем.

Приведём пример использования данного алгоритма:

попробуем выяснить какой НОД у 816 и 252:

1. 816 / 252 = 3 и остаток 60. Сейчас 252 разделим на 60;
2. 252 / 60 = 4 в остатке на этот раз окажется 12. Продолжим наш круговой процесс, разделим шестьдесят на двенадцать;
3. 60 / 12 = 5. Поскольку на сей раз никакого остатка мы не получили, то у нас готов результат, двенадцать будет искомым для нас значением.

Итак, по завершении нашего процесса мы получили НОД (816;252) = 12.

Действия при необходимости определения НОД если задано более двух значений

Мы уже разобрались, что делать в случае, когда имеется два различных числа, теперь научимся действовать, если их имеется 3 и более.

При всей кажущейся сложности, данная задача проблем у нас уже не вызовет. Сейчас мы выбираем два любые числа и определяем искомое для них значение. Следующим шагом отыскиваем НОД у полученного результата и третьего из заданных значений. Затем снова действуем по уже известному нам принципу для четвёртого пятого и так далее.

Заключение

Итак, при кажущейся большой сложности поставленной перед нами изначально задачи, на самом деле все просто, главное уметь выполнять безошибочно процесс делений и придерживаться любого из двух описанных выше алгоритмов.

Хотя оба способа и являются вполне приемлемыми, в общеобразовательной школе гораздо чаще применяется первый способ. Это связано с тем, что разложение на простые множители понадобится при изучении следующей учебной темы — определение наибольшего общего кратного (НОК). Но все же стоит ещё раз заметить — применение алгоритма Евклида ни в коей мере не может считаться ошибочным.

Видео

С помощью видео вы сможете узнать, как найти наибольший общий делитель.

Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 12 и 8, наибольшим общим делителем будет 4.

Как найти НОД?

Способов найти НОД несколько. Мы рассмотрим один из часто используемых в математике — это нахождение НОД при помощи разложения чисел на простые множители. В общем случае алгоритм будет выглядеть следующим образом:

1. разложить оба числа на простые множители (подробнее о разложении чисел на простые множители смотрите тут);
2. выбрать одинаковые множители, входящие в оба разложения;
3. найти их произведение.

Примеры нахождения наибольшего общего делителя

Рассмотрим приведенный алгоритм на конкретных примерах:

Пример 1: найти НОД 12 и 8

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 2 и 2

3. Перемножаем эти множители и получаем: 2 · 2 = 4

Ответ: НОД (8; 12) = 2 · 2 = 4.

Пример 2: найти НОД 75 и 150

Этот пример, как и предыдущий с легкостью можно высчитать в уме и вывести ответ 75, но для лучшего понимания работы алгоритма, проделаем все шаги:

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 3, 5 и 5

3. Перемножаем эти множители и получаем: 3 · 5 · 5 = 75

Ответ: НОД (75; 150) = 3 · 5 · 5 = 75.

Частный случай или взаимно простые числа

Нередко встречаются ситуации, когда оба числа взаимно простые, т.е. общий делитель равен единице. В этом случае, алгоритм будет выглядеть следующим образом:

Пример 3: найти НОД 9 и 5

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

Была ли эта статья полезной?

При решении задач по математике в начальных классах иногда требуется найти наибольший общий делитель, или сокращенно — НОД. Однако не все учащиеся знают правильный алгоритм этой операции, а также путают ее с НОК (наименьшим общим кратным). Чтобы не совершать таких ошибок, специалисты-математики разработали универсальные алгоритмы отличия и нахождения искомых значений.

Оглавление:

• Признаки делимости
• Разложение на простые элементы
• Нахождение НОД
• Определение НОК

При решении задач по математике в начальных классах иногда требуется найти наибольший общий делитель, или сокращенно — НОД. Однако не все учащиеся знают правильный алгоритм этой операции, а также путают ее с НОК (наименьшим общим кратным). Чтобы не совершать таких ошибок, специалисты-математики разработали универсальные алгоритмы отличия и нахождения искомых значений.

Общие сведения

Специалисты перед обучением рекомендуют составить список базовых знаний, необходимых для нахождения наибольшего общего делителя и наименьшего общего кратного. Он состоит из таких элементов:

1. Определения величин.
2. Признаки делимости чисел.
3. Разложение на простые элементы или множители.
4. Алгоритмы или методики нахождения.

НОД — максимальное значение величины, на которую делятся 2 или большее количество чисел. НОК — параметр, характеризующий наименьшее общее делимое. Чтобы понять разницу между этими терминами, нужно разобрать операцию деления двух чисел.

Первый элемент — делимое, т. е. оно делится на определенный элемент (делитель). Результатом является частное. Математики называют последнее частным двух или более значений. Далее нужно разобрать признаки делимости.

Признаки делимости

В математике существуют 2 понятия: цифры и числа. Главное отличие — при комбинации цифр получаются числа. Кроме того, каждое значение состоит из разрядов (единиц, десятков, сотен, тысяч). Последние читаются слева направо, т. е. 657 состоит из единиц (7), десятков (5) и сотен (6). Если объединить их, получится искомая величина. Операция имеет такой вид: 7+50+600=657.

Признаками делимости называются критерии, на основании которых число можно разделить на искомое значение без остатка. К ним относятся следующие правила:

1. R (любое действительное число).
2. Последняя цифра — четная, т. е. 24/2 — делится, т. к. 4 — четное.
3. Сумма цифр, составляющих число, возможно разделить на 3. Пример: 36/3={3+6=9/3=9}=12.
4. Последние 2 цифры можно разделить на 4, т. е. 844/4={44/4=11}=211.
5. Последний разряд эквивалентен одному из двух значений (0 или 5), 810/5={0}=162.
6. Для числа 6 одновременно выполняются второй и третий пункт. Пример: 96/6={6-четное} и {9+6=15/3=15}=16.
7. 7: расчет по формуле [a*b*c*d+e]/7, где e — разряд единиц, а все остальные (слева направо) — десятки, сотни, тысячи и десятки тысяч. Правило справедливо и для величин с разным количеством разрядов. Пример: 861/7={(8*6+1)/7=49/7=7}=123.
8. Деление на 8 осуществляется по второму и четвертому признакам одновременно, т. е. 184/8={4 — четное} и {84/4=21}=23.
9. Сумму разрядов можно разделить на 9. Пример: 108/9={1+0+8=9/9=1}=12.
10. Последняя цифра эквивалентна 0, т. е. 140/10={0}=14.
11. 2 разряда равны между собой (11, 22, 33 и т. д. ) или величина, образованная разрядами сотен и десятков без единиц, делится на 11 (121={(12−1)/11=1}).

Однако признаков делимости недостаточно для перехода к соответствующим алгоритмам. Следующий этап — разложение числа на простые элементы натурального типа.

Разложение на простые элементы

Простые множители — числа, которые делятся только на единицу или на эквивалентную величину, т. е. 7/1 и 7/7. Разложение величины на простые элементы — найти совокупность чисел, произведение которых и будет составлять искомое значение. Например, 30=3*5*2. Для выполнения этой операции математики разработали специальный алгоритм:

1. Написать значение.
2. Определить по признакам делимости первый множитель.
3. Выполнить операцию деления.
4. Подобрать второй множитель для величины, полученной в 3 пункте.
5. Реализовать пункты со 2 по 4 включительно.

Однако для понимания принципа работы алгоритма, нужно выполнить разложение на простые значения на практике. Например, для 176 реализация методики имеет следующий вид:

1. 176.
2. 2: 176/2=88.
3. 11: 88/11=8.
4. 2: 8/2=4.
5. 2: 4/2=2.
6. 2: 2/2=1.

Следовательно, 176=2*11*2*2*2. Однако результат можно записать в более упорядоченной форме: 176=11*2*2*2*2*2. Далее следует перейти к алгоритмам, посредством которых можно вычислить НОК и НОД.

Нахождение НОД

Найти НОД двух чисел можно следующими способами: разложением на простые множители или посредством алгоритма Евклида. Первый имеет такой вид:

1. Раскладываются первое и второе значения на простые множители.
2. Выбираются общие множители и перемножаются между собой.

Для реализации методики на практике нужно разобрать нахождение НОД 86 и 92. Она имеет такой вид:

1. 92: 92/2=46/2=23, т. е. 92=23*2*2.
2. 86: 86/2=43*2.
3. НОД: 2.

Наиболее простой является методика Евклида для нахождения НОД. Она позволяет быстро найти искомое значение и имеет такой вид:

1. Разделить большее значение на меньшее (записать отдельно целую часть и остаток).
2. Если есть остаток, искомое большое число нужно на него разделить.
3. Выполнять пункты алгоритма, пока остаток не будет равным 0. Результат — это и есть НОД.

Чтобы понять смысл, нужно применить ее к числам 92 и 86. Это выглядит следующим образом:

1. 92/86=1{6}.
2. 86/6=14{2}.
3. 14/2=7{0}.
4. НОД=2, т. к. в третьем пункте нет остатка от деления.

Далее нужно рассмотреть методику нахождения НОК, чтобы окончательно понять отличие от НОД.

Определение НОК

НОК находится также посредством разложения на множители, но алгоритм существенно отличается от НОД. Он имеет следующий вид:

1. Разложить величины на множители.
2. Взять наименьшее и дополнить его недостающими элементами.
3. Вычислить искомое значение НОК.

Чтобы понять принцип работы алгоритма, его нужно реализовать на практике. Для числовых значений 18 и 12 он имеет такой вид:

1. 18=3*3*2.
2. 12=2*2*3.
3. НОК=12*3=36.

Следовательно, наименьшим общим кратным двух чисел является 36. Искомую величину нужно находить в алгебре для приведения обыкновенных дробей к общему знаменателю при выполнении арифметических операций сложения и вычитания. Следует отметить, что операцию можно выполнять не только для двух, но и для трех чисел. При этом алгоритм существенно усложняется.

Примеры решения

Одной из сложных задач является следующая: найти наибольший общий делитель чисел 32, 66 и 84. Для решения можно воспользоваться одним из способов. Оптимальным из них является разложение на множители:

1. 32=2*2*2*2*2.
2. 66=11*3*2.
3. 84=2*3*2*2*2*2.
4. НОД=2.

По методике Евклида решать не рекомендуется, т. к. это усложнит вычисления. Основной принцип физико-математических дисциплин — оптимизация расчетов, т. е. нужно искать способ с наименьшим количеством преобразований и расчетов.

В следующей задаче требуется осуществить поиск НОД для 66, 121, 77 и 110. В этом случае также рекомендуется разложить на простые множители все 4 числа. Поиск решения выполняется по такой методике:

1. 66=11*3*2.
2. 121=11*11.
3. 77=11*7.
4. 110=11*5*2.
5. НОД=11.

Если рассмотреть 2 этих примера, можно сделать вывод, что считать НОД довольно просто. Далее нужно найти НОК для 22 и 32. Это осуществляется по такой методике:

1. 22=11*2.
2. 32=8*4=2*2*2*2*2.
3. НОК=11*2*2*2*2*2=22*16=352.

Еще одним типом задачи является одновременное нахождение НОД и НОК для чисел 45, 85, 94 и 96. Решение имеет следующий вид:

1. 45=5*3*3.
2. 85=17*5.
3. 94=2*47.
4. 96=2*2*3*2*2*2.
5. НОД=1 (нет общих множителей, кроме единицы).
6. НОК=5*3*3*17*2*47*2*2*2*2*2=1150560.

В математике встречаются более сложные задачи. Одна из них имеет такую формулировку: НОД двух чисел эквивалентен 9, первое число равно 90 и больше второго. Необходимо найти второе ближайшее целое значение. Решается задание по такому алгоритму:

1. 90=9*10.
2. 81=9*9.
3. НОД=9.

Задача решается методом подбора, поскольку по условию ближайшая целая величина эквивалентна 81.

Таким образом, нахождение НОД является довольно простой операцией, если следовать алгоритму и иметь базовые знания.