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


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

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

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

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

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

Пример 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

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

 

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

Наибольший общий делитель — Математические этюды

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

Для на­хож­де­ния $НОД(a, b)$ мож­но по­сту­пить сле­ду­ю­щим есте­ствен­ным об­ра­зом: раз­ло­жить оба чис­ла по сте­пе­ням про­стых чи­сел: $a = 2^{\alpha_1} \cdot 3^{\alpha_2} \cdot \ldots \cdot p^{\alpha_n}_n$ , $b = 2^{\beta_1} \cdot 3^{\beta_2} \cdot \ldots \cdot p^{\beta_n}_n$ , ($\alpha_k$ и $\beta_k$ мо­гут быть рав­ны ну­лю). То­гда $$НОД(a, b) = 2^{\min(\alpha_1, \beta_1)} \cdot 3^{\min(\alpha_2, \beta_2)} \cdot \ldots \cdot p^{\min(\alpha_n, \beta_n)}_n.$$ На­при­мер, для на­хож­де­ния наи­боль­ше­го об­ще­го де­ли­те­ля $2625$ и $8100$ по­лу­чим: $2625 = 2^0 \cdot 3^1 \cdot 5^3 \cdot 7^1, 8100 = 2^2 \cdot 3^4 \cdot 5^2 \cdot 7^0$, зна­чит $НОД(2625, 8100) = 2^0 \cdot 3^1 \cdot 5^2 \cdot 7^0 = 75$.

Су­ще­ствен­ный недо­ста­ток это­го спо­со­ба в том, что раз­ло­жить боль­шое чис­ло на про­стые мно­жи­те­ли не так про­сто, а точ­нее — не так быст­ро.

Ев­клид в 7 кни­ге «На­чал» опи­сы­ва­ет ал­го­ритм на­хож­де­ния «об­щей ме­ры двух чи­сел». Ал­го­ритм опи­сан гео­мет­ри­че­ски, как на­хож­де­ние об­щей ме­ры двух от­рез­ков. Он сво­дит­ся к «по­сле­до­ва­тель­но­му от­ня­тию» от боль­ше­го от­рез­ка мень­ше­го от­рез­ка. Те­перь этот ал­го­ритм из­ве­стен как ал­го­ритм Ев­кли­да для на­хож­де­ния наи­боль­ше­го об­ще­го де­ли­те­ля двух на­ту­раль­ных чи­сел.

Ос­нов­ная идея, на ко­то­рой ос­но­ван ал­го­ритм, со­сто­ит в том, что $НОД$ чи­сел $a$ и $b$ ра­вен $НОД$ чи­сел $b$ и $a-b$. От­сю­да сле­ду­ют, что ес­ли по­де­лить $a$ на $b$ с остат­ком, т.е. пред­ста­вить в ви­де $a = b \cdot q + r$, то $НОД(a, b) = НОД(b, r)$.

Опи­шем кра­си­вую гео­мет­ри­че­скую ин­тер­пре­та­цию ал­го­рит­ма, ин­тер­ак­тив­ная ре­а­ли­за­ция ко­то­рой пред­ло­же­на вы­ше.

В пря­мо­уголь­ни­ке с дли­на­ми сто­рон $a$ и $b$ за­кра­ши­ва­ем мак­си­маль­но воз­мож­ный квад­рат. В остав­шем­ся пря­мо­уголь­ни­ке сно­ва за­кра­ши­ва­ем мак­си­маль­но воз­мож­ный квад­рат. И так да­лее до тех пор, по­ка весь ис­ход­ный пря­мо­уголь­ник не бу­дет за­кра­шен. Дли­на сто­ро­ны са­мо­го ма­лень­ко­го квад­ра­та и бу­дет рав­на $НОД(a, b)$.

Бо­лее по­дроб­но гео­мет­ри­че­ская ин­тер­пре­та­ция опи­са­на ни­же, а па­рал­лель­но при­ве­де­но ариф­ме­ти­че­ское опи­са­ние ал­го­рит­ма Ев­кли­да.

Ин­тер­пре­та­ция ал­го­рит­ма Ал­го­ритм Ев­кли­да
В пря­мо­уголь­ни­ке с дли­на­ми сто­рон $a$ и $b$ $(a \gt b)$ за­кра­ши­ва­ет­ся квад­рат мак­си­маль­но­го раз­ме­ра (со сто­ро­ной $b$). Эта опе­ра­ция по­вто­ря­ет­ся для не за­кра­шен­ной ча­сти сколь­ко воз­мож­но. Боль­шее чис­ло $a$ де­лит­ся с остат­ком на мень­шее чис­ло $b$: $a = b \cdot q_1 + r_1$.
Ес­ли та­кие квад­ра­ты за­мо­ща­ют весь пря­мо­уголь­ник, то чис­ло $b$ и есть $НОД$. Ес­ли оста­ток $r_1$ от де­ле­ния ра­вен ну­лю, то мень­шее чис­ло $b$ и есть $НОД$.
Ес­ли оста­ёт­ся пря­мо­уголь­ник (со сто­ро­на­ми $b$ и $r_1$), в нём за­кра­ши­ва­ет­ся наи­боль­шее воз­мож­ное чис­ло квад­ра­тов мак­си­маль­но­го раз­ме­ра (со сто­ро­ной $r_1$). Ес­ли оста­ток $r_1$ не ра­вен ну­лю, то мень­шее чис­ло $b$ де­лит­ся с остат­ком на $r_1$: $b = r_1 \cdot q_2 + r_2$.
Ес­ли квад­ра­ты со сто­ро­ной $r_1$ за­мо­ща­ют весь пря­мо­уголь­ник, то $r_1$ и есть $НОД$. Ес­ли в ре­зуль­та­те вто­ро­го де­ле­ния оста­ток $r_2$ ра­вен ну­лю, то $r_1$ и есть $НОД$.
Ес­ли оста­ёт­ся пря­мо­уголь­ник (со сто­ро­на­ми $r_1$ и $r_2$), в нём за­кра­ши­ва­ет­ся наи­боль­шее воз­мож­ное чис­ло квад­ра­тов мак­си­маль­но­го раз­ме­ра (со сто­ро­ной $r_2$). Ес­ли оста­ток $r_2$ при вто­ром де­ле­нии не ра­вен ну­лю, то $r_1$ де­лит­ся на $r_2$: $r_1 = r_2 \cdot q_3 + r_3$.
И так да­лее до тех пор, по­ка весь ис­ход­ный пря­мо­уголь­ник не по­кро­ет­ся квад­ра­та­ми. (Ра­но или позд­но это про­изой­дёт, по­сколь­ку сто­ро­ны квад­ра­тов умень­ша­ют­ся и в лю­бом слу­чае мож­но за­пол­нить остав­ший­ся пря­мо­уголь­ник квад­ра­та­ми со сто­ро­ной еди­ни­ца). И так да­лее до тех пор, по­ка не по­лу­чит­ся оста­ток $r_n$ рав­ный ну­лю (ра­но или позд­но это про­изой­дёт, по­сколь­ку остат­ки умень­ша­ют­ся).
Дли­на сто­ро­ны ми­ни­маль­но­го квад­ра­та и есть $НОД$ ис­ход­ных чи­сел. По­след­ний не рав­ный ну­лю оста­ток $r_{n-1}$ и есть $НОД$ ис­ход­ных чи­сел.

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

Ли­те­ра­ту­ра

Ев­клид. На­ча­ла Ев­кли­да. Кни­ги VII, X. — М.—Л.: ГИТТЛ, 1950.

Р. Ку­рант, Г. Ро­бинс. Что та­кое ма­те­ма­ти­ка? — М.: МЦНМО, 2010.

www.etudes.ru

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

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

НОД (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

Нод и Нок чисел. Разложение на простейшие множители. Примеры вычисление НОК И НОД.

 

Для начала вспомним, что такое простые числа – это числа, которые имеют два делителя: само себя и \(1\). Давайте рассмотрим два числа \(18\) и \(48\) и найдем числа которые будут делится без остатка на них – \(864\) и \(144\). Наименьшее из них \(144\), то есть мы нашли наименьшее общее кратное, сокращенно \(НОК\). Когда мы вычисляем \(НОК\) двух чисел, мы записываем их в круглых скобках \(НОК\)\((48;18).\) А если у нас очень большие числа, как нам тогда искать \(НОК\)? Для этого мы каждое число  должны разложить на простые множители. Взять множители разложения большего числа и недостающие из второго и перемножить их.

НОК\((48;18)=2*3*4*2*3=144.\)

Давайте найдем \(НОК\) у \(7\) и \(9\). Раскладываем на простые множители:

\(7\) и \(17\) – это простые числа, так как они делятся на себя и на \(1\), то есть общий делитель у них \(1\). Два числа называются взаимно простыми, если у них нет общих делителей, кроме числа \(1\). Как же нам в этом случае найти \(НОК\)? Применяем все те же правила. Берем простые множители из наибольшего числа и недостающие из второго и затем перемножаем их.  \(НОК\) чисел \(17\) и \(7\)  равен их произведению, то есть \(119\). Можно сформулировать простое правило для нахождения \(НОК\) у взаимно простых чисел:

Чтобы найти \(НОК\) у взаимно простых чисел, мы должны перемножить их. Легко, не так ли?

Задача 1. Найти \(НОК\)(840;140).

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

Заметив, что множители в числе \(140\) повторяются, берем множители разложение большего числа: \(2*2*3*5*7*2=840.\)

Ответ: \(НОК\)\((840;140)=840.\)

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

Задача 2. Найти \(НОД\)(840;140).

Решение. Выше можно посмотреть разложение этих чисел на простые множители.

Общие множители это 2*5*2*7=140.

Ответ: \(НОД\)(840;140)=140.

 

 

 

 

 

 

 

Больше уроков и заданий по математике вместе с преподавателями нашей онлайн-школы "Альфа". Запишитесь на пробное занятие уже сейчас!

Запишитесь на бесплатное тестирование знаний!

myalfaschool.ru

НОД и НОК трех и более чисел

НОД (Факторизованный вид)
Наибольший общий делитель
НОК (Факторизованный вид)
Наименьшее общее кратное
НОД (Числовое значение)
Наибольший общий делитель
НОК (Числовое значение)
Наименьшее общее кратное

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

НОК - наименьшее общее кратное. Такое число, на которое без остатка будет делится все заданные числа.

Например,  если заданные числа 2, 3, 5, то НОК=2*3*5=30

А если заданные числа  2,4,8, то НОК =8

что такое НОД?

НОД - наибольший общий делитель. Такое число, которым  можно разделить каждое из заданных чисел, без остатка.

Логично что  если заданные числа будут простыми, то НОД равен единице.

А если  заданны числа 2, 4, 8 то НОД равен 2.

НОД можно рассчитать по методу Евклида.

Расписывать его в общем виде не будем, а просто покажем решение на примере.

Заданы два числа 126 и 44. Найти НОД.

1. Делим 126 на 44 и находим остаток от деления  126=44*2+38. Остаток 38

2.Делим 44 на 38 и находим остаток. Он равен 6

3. Делим 38 на 6 и определим остаток. Остаток равен 2

4. Делим 6 на 2 и видим что он делится нацело, то есть с нулевым остатком.

Смотрим какое же было предыдущий остаток (на 3 вычислении). Видим что он равен 2

НОД этих двух чисел равен 2.

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

Для этого нам надо каждое число преобразовать в произведение сомножителей. Как это сделано в материале Простые множители. Теория чисел

Тогда если нам даны два числа вида

и

То НОД высчитывается как 

где min - минимальное значение  из всех значений степеней числа pn

а НОК  как 

где max - максимальное значение  из всех значений степеней числа pn

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

Поэтому легко ответить на вопрос чему равен НОД вот таких чисел  3,  25412, 3251, 7841, 25654, 7  ничего не вычисляя.

числа 3 и 7 взаимно простые, а следовательно НОД=1

Рассмотрим пример.

Даны три числа 24654, 25473 и 954

Каждое число  раскладывается в следующие множители

Или, если мы запишем в альтернативном виде

 

 

 

 

Теперь легко высчитать НОД по формуле

 

 

 

 

То есть НОД этих трех чисел равен трем

 

Ну а НОК можем вычислить аналогично, и он равен

 

 

Наш бот, поможет Вам вычислить НОД и НОК любых целых чисел, двух, трех или десяти.

 

Удобство нашего бота не только в легкости ввода, но и  в выведении результата.

 

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

 

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

 

Ограничение только одно, кажое число не должно быть длиннее 15 символов

 

Удачных расчетов!

 

  • Нормальное интегральное распределение >>

www.abakbot.ru

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

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

Математика для многих - не самый легкий предмет. Уж сколько непонятных формул и теорем она в себе таит! И все это каким-то чудом должны не только запомнить, но и понять ученики. Мы попробуем сделать эту науку для вас немного понятнее, научив, как найти НОД чисел.

Решение задач

Наибольший общий делитель, или попросту НОД, – это показатель, который вычисляется для двух и более чисел. Как известно, число, на которое другое число делится без остатка, называется делителем. Таких чисел для каждого числа как минимум два: 1 и оно само. Такие числа называют простыми. К ним относятся 2, 3, 5, 7, 11, 13, 17, 19, 23 и т. д. Но у большинства чисел существует три и больше делителя. Для числа 10 это цифры 1, 2, 5, 10; для 8 – 1, 2 , 4, 8.

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

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

Давайте сразу посмотрим, как найти НОД на конкретном примере. Допустим, нам даны цифры 124 и 72.

124|2 72|2
62|2 36|2
31|31 18|2
1|1 9|3
  3|3
  1|1

Затем надо подчеркнуть одинаковые общие множители в обоих числах:

Чтобы найти НОД, перемножьте общие простые множители. В нашем случае:

  • НОД (72; 124) = 2 х 2 = 4

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

Есть ряд чисел, которые называют взаимно простыми. Они не имеют между собою других общих делителей, кроме 1. Поэтому их НОД равен 1. Например, таковы числа 49 и 8. Простые множители 49 = 7 х 7 х 1; 8 = 2 х 2 х 2х 2 х 1. Как видите, из всех цифр у них общая одна – единица.

Онлайн-калькулятор

Также можно воспользоваться специальными о

elhow.ru