Кратные числа онлайн. Общий делитель и кратное

Множество делителей

Рассмотрим такую задачу: найти делитель числа 140. Очевидно, что у числа 140 не один делитель, а несколько. В таких случаях говорят, что задача имеет множество решений. Найдем их все. Прежде всего разложим данное число на простые множители:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Теперь мы без труда можем выписать все делители. Начнем с простых делителей, то есть тех, которые присутствуют в разложении, приведенном выше:

Затем выпишем те, которые получаются попарным умножением простых делителей:

2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.

Затем - те, которые содержат в себе три простых делителя:

2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.

Наконец, не забудем единицу и само разлагаемое число:

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

Множество делителей числа 140 =

{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

Для удобства восприятия мы выписали здесь делители (элементы множества ) в порядке возрастания, но, вообще говоря, это делать необязательно. Кроме того, введем сокращение записи. Вместо «Множество делителей числа 140» будем писать «Д(140)». Таким образом,

Точно так же можно найти множество делителей для любого другого натурального числа. Например, из разложения

105 = 3 ∙ 5 ∙ 7

мы получаем:

Д(105) = {1, 3, 5, 7, 15, 21, 35, 105}.

От множества всех делителей следует отличать множество простых делителей, которые для чисел 140 и 105 равны соответственно:

ПД(140) = {2, 5, 7}.

ПД(105) = {3, 5, 7}.

Следует особо подчеркнуть, что в разложении числа 140 на простые множители двойка присутствует два раза, в то время как во множестве ПД(140) - только один. Множество ПД(140) - это, по своей сути, все ответы на задачу: «Найти простой множитель числа 140». Ясно, что один и тот же ответ не следует повторять больше одного раза.

Сокращение дробей. Наибольший общий делитель

Рассмотрим дробь

Мы знаем, что эту дробь можно сократить на такое число, которое одновременно является и делителем числителя (105) и делителем знаменателя (140). Взглянем на множества Д(105) и Д(140) и выпишем их общие элементы.

Д(105) = {1, 3, 5, 7, 15, 21, 35, 105};

Д(140) = {1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

Общие элементы множеств Д(105) и Д(140) =

Последнее равенство можно записать короче, а именно:

Д(105) ∩ Д(140) = {1, 5, 7, 35}.

Здесь специальный значок «∩» («мешок отверстием вниз») как раз и указывает на то, что из двух множеств, записанных по разные стороны от него, надо выбрать только общие элементы. Запись «Д(105) ∩ Д(140)» читается «пересечение множеств Дэ от 105 и Дэ от 140».

[Заметим по ходу дела, что с множествами можно производить разные бинарные операции, почти как с числами. Другой распространенной бинарной операцией является объединение , которое обозначается значком «∪» («мешок отверстием вверх»). В объединение двух множеств входят все элементы как того, так и другого множества:

ПД(105) = {3, 5, 7};

ПД(140) = {2, 5, 7};

ПД(105) ∪ ПД(140) = {2, 3, 5, 7}. ]

Итак, мы выяснили, что дробь

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

Д(105) ∩ Д(140) = {1, 5, 7, 35}

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

Очевидно, что практичнее всего сокращать дробь на число, по возможности большее. В данном случае это число 35, про которое говорят, что оно является наибольшим общим делителем (НОД ) чисел 105 и 140. Это записывается как

НОД(105, 140) = 35.

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

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Перемножая подчеркнутые числа (в любом из разложений), получаем:

НОД(105, 140) = 5 ∙ 7 = 35.

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

168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;

396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.

Отсюда видно, что

НОД(168, 396) = 2 ∙ 2 ∙ 3 = 12.

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

42 = 2 ∙ 3 ∙ 7;

В этом случае,

НОД(42, 55) = 1.

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

то такая дробь является несократимой .

Вообще говоря, правило сокращения дробей можно записать в таком виде:

Здесь предполагается, что a и b - натуральные числа, а вся дробь положительна. Если мы теперь припишем знак «минус» к обоим частям этого равенства, то получим соответствующее правило для отрицательных дробей.

Сложение и вычитание дробей. Наименьшее общее кратное

Пусть требуется вычислить сумму двух дробей:

Мы уже знаем, как раскладываются на простые множители знаменатели:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Из этого разложения сразу следует, что, для того чтобы привести дроби к общему знаменателю, достаточно числитель и знаменатель первой дроби умножить на 2 ∙ 2 (произведение неподчеркнутых простых множителей второго знаменателя), а числитель и знаменатель второй дроби - на 3 («произведение» неподчеркнутых простых множителей первого знаменателя). В результате знаменатели обеих дробей станут равны числу, которое можно представить так:

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.

Нетрудно видеть, что оба исходных знаменателя (как 105, так и 140) являются делителями числа 420, а число 420, в свою очередь, кратно обоим знаменателям, - и не просто кратно, оно является наименьшим общим кратным (НОК ) чисел 105 и 140. Это записывается так:

НОК(105, 140) = 420.

Приглядевшись повнимательнее к разложению чисел 105 и 140, мы видим, что

105 ∙ 140 = НОК(105, 140) ∙ НОД(105, 140).

Точно так же, для произвольных натуральных чисел b и d :

b ∙ d = НОК(b , d ) ∙ НОД(b , d ).

Теперь давайте доведем до конца суммирование наших дробей:

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

Калькулятор для нахождения НОД и НОК

Найти НОД и НОК

Найдено НОД и НОК: 5806

Как пользоваться калькулятором

• Введите числа в поле для ввода
• В случае ввода некорректных символов поле для ввода будет подсвечено красным
• нажмите кнопку "Найти НОД и НОК"

Как вводить числа

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

Что такое НОД и НОК?

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

Как проверить, что число делится на другое число без остатка?

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

Некоторые признаки делимости чисел

1. Признак делимости числа на 2
Чтобы определить, делится ли число на два (является ли оно чётным), достаточно посмотреть на последнююю цифру этого числа: если она равна 0, 2, 4, 6 или 8, то число чётно, а значит делится на 2.
Пример: определить, делится ли на 2 число 34938 .
Решение: смотрим на последнюю цифру: 8 - значит число делится на два.

2. Признак делимости числа на 3
Число делится на 3 тогда, когда сумма его цифр делится на три. Таким образом, чтобы определить, делится ли число на 3, нужно посчитать сумму цифр и проверить, делится ли она на 3. Даже если сумма цифр получилась очень большой, можно повторить этот же процесс вновь.
Пример: определить, делится ли число 34938 на 3.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 3, а значит и число делится на три.

3. Признак делимости числа на 5
Число делится на 5 тогда, когда его последняя цифра равна нулю или пяти.
Пример: определить, делится ли число 34938 на 5.
Решение: смотрим на последнюю цифру: 8 - значит число НЕ делится на пять.

4. Признак делимости числа на 9
Этот признак очень похож на признак делимости на тройку: число делится на 9 тогда, когда сумма его цифр делится на 9.
Пример: определить, делится ли число 34938 на 9.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 9, а значит и число делится на девять.

Как найти НОД и НОК двух чисел

Как найти НОД двух чисел

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

Рассмотрим этот способ на примере нахождения НОД(28, 36) :

1. Раскладываем оба числа на множители: 28 = 1·2·2·7 , 36 = 1·2·2·3·3
2. Находим общие множители, то есть те, которые есть у обоих чисел: 1, 2 и 2.
3. Вычисляем произведение этих множителей: 1·2·2 = 4 - это и есть наибольший общий делитель чисел 28 и 36.

Как найти НОК двух чисел

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

Для вычисления НОК нужно вычислить произведение исходных чисел и затем разделить его на предварительно найденный НОД. Найдём НОК для тех же чисел 28 и 36:

1. Находим произведение чисел 28 и 36: 28·36 = 1008
2. НОД(28, 36), как уже известно, равен 4
3. НОК(28, 36) = 1008 / 4 = 252 .

Нахождение НОД и НОК для нескольких чисел

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

Аналогичное соотношение действует и для наименьшего общего кратного чисел: НОК(a, b, c) = НОК(НОК(a, b), c)

Пример: найти НОД и НОК для чисел 12, 32 и 36.

1. Cперва разложим числа на множители: 12 = 1·2·2·3 , 32 = 1·2·2·2·2·2 , 36 = 1·2·2·3·3 .
2. Найдём обшие множители: 1, 2 и 2 .
3. Их произведение даст НОД: 1·2·2 = 4
4. Найдём теперь НОК: для этого найдём сначала НОК(12, 32): 12·32 / 4 = 96 .
5. Чтобы найти НОК всех трёх чисел, нужно найти НОД(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , НОД = 1·2·2·3 = 12 .
6. НОК(12, 32, 36) = 96·36 / 12 = 288 .

Второе число: b=

Разделитель разрядов Без разделителя пробел " ´

Результат:

Наибольший общий делитель НОД(a ,b )=6

Наименьшее общее кратное НОК(a ,b )=468

Наибольшее натуральное число, на которое делятся без остатка числа a и b, называется наибольшим общим делителем (НОД) этих чисел. Обозначается НОД(a,b), (a,b), gcd(a,b) или hcf(a,b).

Наименьшее общее кратное (НОК) двух целых чисел a и b есть наименьшее натуральное число, которое делится на a и b без остатка. Обозначается НОК(a,b), или lcm(a,b).

Целые числа a и b называются взаимно простыми , если они не имеют никаких общих делителей кроме +1 и −1.

Наибольший общий делитель

Пусть даны два положительных числа a 1 и a 2 1). Требуется найти общий делитель этих чисел, т.е. найти такое число λ , которое делит числа a 1 и a 2 одновременно. Опишем алгоритм.

1) В данной статье под словом число будем понимать целое число.

Пусть a 1 ≥ a 2 , и пусть

где m 1 , a 3 некоторые целые числа, a 3 <a 2 (остаток от деления a 1 на a 2 должен быть меньше a 2).

Предположим, что λ делит a 1 и a 2 , тогда λ делит m 1 a 2 и λ делит a 1 −m 1 a 2 =a 3 (Утверждение 2 статьи "Делимость чисел. Признак делимости"). Отсюда следует, что всякий общий делитель a 1 и a 2 является общим делителем a 2 и a 3 . Справедливо и обратное, если λ общий делитель a 2 и a 3 , то m 1 a 2 и a 1 =m 1 a 2 +a 3 также делятся на λ . Следовательно общий делитель a 2 и a 3 есть также общий делитель a 1 и a 2 . Так как a 3 <a 2 ≤a 1 , то можно сказать, что решение задачи по нахождению общего делителя чисел a 1 и a 2 сведено к более простой задаче нахождения общего делителя чисел a 2 и a 3 .

Если a 3 ≠0, то можно разделить a 2 на a 3 . Тогда

,

где m 1 и a 4 некоторые целые числа, (a 4 остаток от деления a 2 на a 3 (a 4 <a 3)). Аналогичными рассуждениями мы приходим к выводу, что общие делители чисел a 3 и a 4 совпадают с общими делителями чисел a 2 и a 3 , и также с общими делителями a 1 и a 2 . Так как a 1 , a 2 , a 3 , a 4 , ... числа, постоянно убывающие, и так как существует конечное число целых чисел между a 2 и 0, то на каком то шаге n , остаток от деления a n на a n+1 будет равен нулю (a n+2 =0).

.

Каждый общий делитель λ чисел a 1 и a 2 также делитель чисел a 2 и a 3 , a 3 и a 4 , .... a n и a n+1 . Справедливо и обратное, общие делители чисел a n и a n+1 являются также делителями чисел a n−1 и a n , .... , a 2 и a 3 , a 1 и a 2 . Но общий делитель чисел a n и a n+1 является число a n+1 , т.к. a n и a n+1 без остатка делятся на a n+1 (вспомним, что a n+2 =0). Следовательно a n+1 является и делителем чисел a 1 и a 2 .

Отметим, что число a n+1 является наибольшим из делителей чисел a n и a n+1 , так как наибольший делитель a n+1 является сам a n+1 . Если a n+1 можно представить в виде произведения целых чисел, то эти числа также являются общими делителями чисел a 1 и a 2 . Число a n+1 называют наибольшим общим делителем чисел a 1 и a 2 .

Числа a 1 и a 2 могут быть как положительными, так и отрицательными числами. Если один из чисел равен нулю, то наибольший общий делитель этих чисел будет равен абсолютной величине другого числа. Наибольший общий делитель нулевых чисел не определен.

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

Пример нахождения наибольшего общего делителя двух чисел

Найти наибольший общий делитель двух чисел 630 и 434.

• Шаг 1. Делим число 630 на 434. Остаток 196.
• Шаг 2. Делим число 434 на 196. Остаток 42.
• Шаг 3. Делим число 196 на 42. Остаток 28.
• Шаг 4. Делим число 42 на 28. Остаток 14.
• Шаг 5. Делим число 28 на 14. Остаток 0.

На шаге 5 остаток от деления равен 0. Следовательно наибольший общий делитель чисел 630 и 434 равен 14. Заметим, что числа 2 и 7 также являются делителями чисел 630 и 434.

Взаимно простые числа

Определение 1. Пусть наибольший общий делитель чисел a 1 и a 2 равен единице. Тогда эти числа называются взаимно простыми числами , не имеющими общего делителя.

Теорема 1. Если a 1 и a 2 взаимно простые числа, а λ какое то число, то любой общий делитель чисел λa 1 и a 2 является также общим делителем чисел λ и a 2 .

Доказательство. Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя чисел a 1 и a 2 (см. выше).

.

Из условия теоремы следует, что наибольшим общим делителем чисел a 1 и a 2 , и следовательно a n и a n+1 является 1. Т.е. a n+1 =1.

Умножим все эти равенства на λ , тогда

.

Пусть общий делитель a 1 λ и a 2 есть δ . Тогда δ входит множителем в a 1 λ , m 1 a 2 λ и в a 1 λ -m 1 a 2 λ =a 3 λ (см. "Делимость чисел",Утверждение 2). Далее δ входит множителем в a 2 λ и m 2 a 3 λ , и, следовательно, входит множителем в a 2 λ -m 2 a 3 λ =a 4 λ .

Рассуждая так мы убеждаемся, что δ входит множителем в a n−1 λ и m n−1 a n λ , и, следовательно, в a n−1 λ −m n−1 a n λ =a n+1 λ . Так как a n+1 =1, то δ входит множителем в λ . Следовательно число δ является общим делителем чисел λ и a 2 .

Рассмотрим частные случаи теоремы 1.

Следствие 1. Пусть a и c простые числа относительно b . Тогда их произведение ac является простым числом относительно b .

Действительно. Из теоремы 1 ac и b имеют тех же общих делителей, что и c и b . Но числа c и b взаимно простые, т.е. имеют единственный общий делитель 1. Тогда ac и b также имеют единственный общий делитель 1. Следовательно ac и b взаимно простые.

Следствие 2. Пусть a и b взаимно простые числа и пусть b делит ak . Тогда b делит и k .

Действительно. Из условия утверждения ak и b имеют общий делитель b . В силу теоремы 1, b должен быть общим делителем b и k . Следовательно b делит k .

Следствие 1 можно обобщить.

Следствие 3. 1. Пусть числа a 1 , a 2 , a 3 , ..., a m простые относительно числа b . Тогда a 1 a 2 , a 1 a 2 ·a 3 , ..., a 1 a 2 a 3 ···a m , произведение этих чисел простое относительно числа b .

2. Пусть имеем два ряда чисел

таких, что каждое число первого ряда простое по отношению каждого числа второго ряда. Тогда произведение

Требуется найти такие числа, которые делятся на каждое из этих чисел.

Если число делится на a 1 , то оно имеет вид sa 1 , где s какое-нибудь число. Если q есть наибольший общий делитель чисел a 1 и a 2 , то

где s 1 - некоторое целое число. Тогда

является наименьшим общим кратным чисел a 1 и a 2 .

a 1 и a 2 взаимно простые, то наименьшее общее кратное чисел a 1 и a 2:

Нужно найти наименьшее общее кратное этих чисел.

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

В частном случае, когда числа a 1 , a 2 , a 3 ,...,a m взаимно простые, то наименьшее общее кратное чисел a 1 , a 2 как было показано выше имеет вид (3). Далее, так как a 3 простое по отношению к числам a 1 , a 2 , тогда a 3 простое по отношению числа a 1 ·a 2 (Следствие 1). Значит наименьшее общее кратное чисел a 1 ,a 2 ,a 3 является число a 1 · a 2 ·a 3 . Рассуждая аналогичным образом мы приходим к следующим утверждениям.

Утверждение 1. Наименьшее общее кратное взаимно простых чисел a 1 , a 2 , a 3 ,...,a m равен их произведению a 1 ·a 2 ·a 3 ···a m .

Утверждение 2. Любое число, которое делится на каждое из взаимно простых чисел a 1 , a 2 , a 3 ,...,a m делится также на их произведение a 1 ·a 2 ·a 3 ···a m .

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

Навигация по странице.

Алгоритм Евклида для нахождения НОД

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

Ответ:

НОД(661, 113)=1 .

Нахождение НОД с помощью разложения чисел на простые множители

Рассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители . Сформулируем правило: НОД двух целых положительных чисел a и b равен произведению всех общих простых множителей, находящихся в разложениях чисел a и b на простые множители .

Приведем пример для пояснения правила нахождения НОД. Пусть нам известны разложения чисел 220 и 600 на простые множители, они имеют вид 220=2·2·5·11 и 600=2·2·2·3·5·5 . Общими простыми множителями, участвующими в разложении чисел 220 и 600 , являются 2 , 2 и 5 . Следовательно, НОД(220, 600)=2·2·5=20 .

Таким образом, если разложить числа a и b на простые множители и найти произведение всех их общих множителей, то этим будет найден наибольший общий делитель чисел a и b .

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

Пример.

Найдите наибольший общий делитель чисел 72 и 96 .

Решение.

Разложим на простые множители числа 72 и 96 :

То есть, 72=2·2·2·3·3 и 96=2·2·2·2·2·3 . Общими простыми множителями являются 2 , 2 , 2 и 3 . Таким образом, НОД(72, 96)=2·2·2·3=24 .

Ответ:

НОД(72, 96)=24 .

В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что НОД(m·a 1 , m·b 1)=m·НОД(a 1 , b 1) , где m – любое целое положительное число.

Нахождение НОД трех и большего количества чисел

Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a 1 , a 2 , …, a k равен числу d k , которое находится при последовательном вычислении НОД(a 1 , a 2)=d 2 , НОД(d 2 , a 3)=d 3 , НОД(d 3 , a 4)=d 4 , …, НОД(d k-1 , a k)=d k .

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

Пример.

Найдите наибольший общий делитель четырех чисел 78 , 294 , 570 и 36 .

Решение.

В этом примере a 1 =78 , a 2 =294 , a 3 =570 , a 4 =36 .

Сначала по алгоритму Евклида определим наибольший общий делитель d 2 двух первых чисел 78 и 294 . При делении получаем равенства 294=78·3+60 ; 78=60·1+18 ; 60=18·3+6 и 18=6·3 . Таким образом, d 2 =НОД(78, 294)=6 .

Теперь вычислим d 3 =НОД(d 2 , a 3)=НОД(6, 570) . Опять применим алгоритм Евклида: 570=6·95 , следовательно, d 3 =НОД(6, 570)=6 .

Осталось вычислить d 4 =НОД(d 3 , a 4)=НОД(6, 36) . Так как 36 делится на 6 , то d 4 =НОД(6, 36)=6 .

Таким образом, наибольший общий делитель четырех данных чисел равен d 4 =6 , то есть, НОД(78, 294, 570, 36)=6 .

Ответ:

НОД(78, 294, 570, 36)=6 .

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

Пример.

Вычислите НОД чисел из предыдущего примера, используя их разложения на простые множители.

Решение.

Разложим числа 78 , 294 , 570 и 36 на простые множители, получаем 78=2·3·13 , 294=2·3·7·7 , 570=2·3·5·19 , 36=2·2·3·3 . Общими простыми множителями всех данных четырех чисел являются числа 2 и 3 . Следовательно, НОД(78, 294, 570, 36)=2·3=6 .

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

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

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

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

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

Большинство натуральных чисел могут делиться не только на единицу, самих себя, но и на другие числа. Так, например, число 15 можно поделить еще на 3 и 5. Все их называют делителями числа 15.

Таким образом, делитель любого А - это число, на которое оно может быть разделено без остатка. Если у числа имеется более двух натуральных делителей, его называют составным.

У числа 30 можно выделить такие делители, как 1, 3, 5, 6, 15, 30.

Можно заметить, что 15 и 30 имеют одинаковые делители 1, 3, 5, 15. Наибольший общий делитель этих двух чисел - 15.

Таким образом, общим делителем чисел А и Б называется такое число, на которое можно поделить их нацело. Наибольшим можно считать максимальное общее число, на которое можно их разделить.

Для решения задач используется такая сокращенная надпись:

НОД (А; Б).

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

Чтобы записать все делители натурального числа, применяется запись:

Д (15) = {1, 3, 5, 15}

НОД (9; 15) = 1

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

Как найти наибольший общий делитель чисел

Чтобы найти НОД нескольких чисел, нужно:

Найти все делители каждого натурального числа по отдельности, то есть разложить их на множители (простые числа);

Выделить все одинаковые множители у данных чисел;

Перемножить их между собой.

Например, чтобы вычислить наибольший общий делитель чисел 30 и 56, нужно записать следующее:

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

Так, в правом столбце окажутся все нужные для решения множители.

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

НОД (30; 56) = 2 * 5 = 10

Вот так просто на самом деле найти наибольший общий делитель чисел. Если немного потренироваться, делать это можно будет практически на автомате.