Как находить наибольший общий делитель (НОД) двух чисел. Как находится наибольший общий делитель


НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ, алгоритм как найти НОД

Наибольший общий делитель чисел – это наибольшее число, на которое делятся все заданные числа.

Алгоритм поиска НОД

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

  1. Разложить все числа на простые множители, используя признаки делимости чисел.
  2. Найти совпадающие множители во всех числах и выписать их.
  3. Перемножить совпадающие множители.

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

Примеры поиска наибольшего общего делителя

Рассмотрим, как найти НОД с помощью алгоритма на нескольких примерах.

Пример 1:

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

Решение:

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

Получили, что:

420 = 2 ⋅ 2 ⋅ 3 ⋅ 5 ⋅ 7

990 = 2 ⋅ 3 ⋅ 3 ⋅ 5 ⋅ 11

Выпишем все совпадающие множители для обоих чисел и перемножим их:

НОД = 2 ⋅ 3 ⋅ 5 = 30

Ответ: 30

Пример 2:

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

Решение:

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

Получили, что:

588 = 2 ⋅ 2 ⋅ 3 ⋅ 7 ⋅ 7

1820 = 2 ⋅ 2 ⋅ 5 ⋅ 7 ⋅ 13

Выпишем все совпадающие множители для обоих чисел и перемножим их:

НОД = 2 ⋅ 2 ⋅ 7 = 28

Ответ: 28

Пример 3:

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

Решение:

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

Получили, что:

1000 = 2 ⋅ 2 ⋅ 2 ⋅ 5 ⋅ 5 ⋅ 5

3267 = 3 ⋅ 3 ⋅ 3 ⋅ 11 ⋅ 11

Совпадающих множителей у этих 2 чисел нет, поэтому они являются взаимно простыми, то есть

Ответ: 1

worksbase.ru

Как найти наибольший общий делитель (НОД)

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

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

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

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

Пример 1. Найдём НОД (84, 90).

Раскладываем числа 84 и 90 на простые множители:

Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой: 1 · 2 · 3 = 6.

Таким образом, НОД (84, 90) = 6.

Пример 2. Найдём НОД (15, 28).

Раскладываем 15 и 28 на простые множители:

Числа 15 и 28 являются взаимно простыми, так как их наибольший общий делитель – единица.

НОД (15, 28) = 1.

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

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

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

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

Пример 1. Возьмём два числа 27 и 9. Так как 27 делится на 9 и 9 делится на 9, значит, 9 является общим делителем чисел 27 и 9. Этот делитель является в тоже время и наибольшим, потому что 9 не может делиться ни на какое число, большее 9. Следовательно, НОД (27, 9) = 9.

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

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

Пример 2. Найдём наибольший общий делитель чисел 140 и 96:

1) 140 : 96 = 1 (остаток 44)

2) 96 : 44 = 2 (остаток 8)

3) 44 : 8 = 5 (остаток 4)

4) 8 : 4 = 2

Последний делитель равен 4 – это значит, что НОД (140, 96) = 4.

Последовательное деление так же можно записывать столбиком:

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

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

Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа – 48:

1) 48 : 4 = 12

48 делится на 4 без остатка. Таким образом, НОД (140, 96, 48) = 4.

naobumium.info

Наибольший общий делитель, НОД | Формулы с примерами

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

НОД (a,b) - самое большое натуральное число, на которое делится и a и b.

Найдем НОД из примера

Делители числа 12 : 1, 2, 3 , 4, 6, 12.

Делители числа 18 : 1, 2, 3, 6, 9, 18.

Общий делитель чисел 12 и 18 : 1, 2, 3, 6.

Наибольший из общих делителей - 6.

Значит, НОД (12, 18) = 6.

Пример
НОД (8, 20) = 4;

НОД (10, 50) = 10;

НОД (4, 94) = 2;

Схема нахождения НОД (a, b)

1. Разложить a и b на простые множители.

2. Подчеркнуть общие множители этих разложений.

3. Перемножить все подчеркнутые множители одного из чисел.

Пример
a = 72 = 2 • 2 • 2 • 3 • 3;

b = 96 = 2• 2• 2 • 2 • 2 • 3;

НОД (72, 96) = 2 • 2 • 2 • 3 = 24.

Пример
a = 630 = 2 • 3 • 3 • 5 • 7;

b = 3675 = 3 • 5 • 5 • 7 • 7;

НОД (630, 3675) = 3 • 5 • 7 = 105.

! Схема подходит и для нахождения НОД трех и более чисел.

Пример
220 = 2 • 2 • 5 • 11;

105 = 3 • 5 • 7;

30 = 2 • 3 • 5;

НОД (220, 105, 30) = 5.

Найдем наибольший общий делитель другим способом

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

1. Разложим 2 числа (12 и 18) на простые множители;

2. Оставляем равные множители;

3. Находим произведение множителей первой и второй группы;

Аналогичным образом можно найти наибольший общий делитель для 3, 4, 5 и более чисел.

formula-xyz.ru

Наибольший общий делитель (НОД): определение, как найти, схема

 

Решим задачу. У нас есть  два типа печенья. Одни шоколадные, а другие простые. Шоколадных 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. Посчитать произведение оставшихся множителей.

Нужна помощь в учебе?

Предыдущая тема: Простые и составные числа: разложение чисел на простые множители Следующая тема:&nbsp&nbsp&nbspНаименьшее общее кратное (НОК): определение, как найти, общая схема

Все неприличные комментарии будут удаляться.

www.nado5.ru

Что такое наибольший общий делитель двух чисел (НОД) и методика как его находить

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

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

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

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

  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 и более.

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

Заключение

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

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

Видео

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

liveposts.ru

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

Стр 1 из 4Следующая ⇒

Определение наибольшего общего делителя

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

Кратко наибольший общий делитель чисел a и b записывают так: НОД (a; b).

Пример: НОД (12; 36) = 12.

Некоторые пары чисел, например числа 24 и 35, имеют в качестве наибольшего общего делителя единицу. Такие числа называют взаимно простыми числами.

Взаимно простые числа - это натуральные числа, которые имеют только один общий делитель - число 1. Их НОД равен 1.

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

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

Первый способ:

Найти НОД 48 и 36.

  1. Разложить делители чисел на простые множители

  1. Подчёркиваем одинаковые простые множители в обоих числах.
  2. Находим произведение одинаковых простых множителей и записать ответ. НОД (36; 48) = 2 • 2 = 4

Второй способ:

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

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. Посчитать произведение оставшихся множителей.

Наименьшее общее кратное (НОК)

Рассмотрим решение следующей задачи. Шаг мальчика составляет 75 см, а шаг девочки 60 см. Необходимо найти наименьшее расстояние, на котором они оба сделают по целому числу шагов.

Решение. Весь путь который пройдут ребята, должен делиться без остатка на 60 и на 70, так как они должны сделать каждый целое число шагов. Другими словами, в ответе должно быть число, кратное как 75 так и 60.

Сначала будем выписывать все кратные числа, для числа 75.

60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, … .

Теперь находим числа которые есть в обоих рядах. Общими кратными чисел будут числа, 300, 600, и т.д.

Самое наименьшее из них, это число 300. Оно в данном случае будет называться наименьшим общим кратным чисел 75 и 60.

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

Кратко наименьшее общее кратное чисел a и b записывают так: НОК (a; b).

Пример: НОК (6, 8) = 24

Возвращаясь к условию задачи, наименьшее расстояние, на котором ребята сделают целое число шагов будет 300 см. Мальчик пройдет этот путь за 4 шага, а девочке потребуется сделать 5 шагов.

 

 

mykonspekts.ru

НОД и НОК чисел с решением | Наибольший общий делитель и наименьшее общее кратное нескольких чисел

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

programforyou.ru