Рассмотрим два основных метода нахождения НОД двумя основными способами: с использованием алгоритма Евклида и путем разложения на простые множители. Применим оба метода для двух, трех и большего количества чисел.
Алгоритм Евклида для нахождения НОД
Алгоритм Евклида позволяет с легкостью вычислить наибольший общий делитель для двух положительных чисел. Формулировки и доказательство алгоритма Евклида мы привели в разделе «Наибольший общий делитель: определитель, примеры».
Суть алгоритма заключается в том, чтобы последовательно проводить деление с остатком, в ходе которого получается ряд равенств вида:
a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1
Мы можем закончить деление тогда, когда rk+1=0, при этом rk=НОД(a, b).
Найдите наибольший общий делитель чисел 64 и 48.
Решение
Введем обозначения: a=64, b=48.
На основе алгоритма Евклида проведем деление 64 на 48.
Получим 1 и остаток 16. Получается, что q1=1, r1=16.
Вторым шагом разделим 48 на 16, получим 3. То есть q2=3, а r2=0. Таким образом число 16 – это наибольший общий делитель для чисел из условия.
Ответ: НОД(64, 48)=16.
Чему равен НОД чисел 111 и 432?
Решение
Делим 432 на 111. Согласно алгоритму Евклида получаем цепочку равенств 432=111·3+99, 111=99·1+12, 99=12·8+3, 12=3·4.
Таким образом, наибольший общий делитель чисел 111 и 432 – это 3.
Ответ: НОД(111, 432)=3.
Найдите наибольший общий делитель чисел 661 и 113.
Решение
Проведем последовательно деление чисел и получим НОД(661, 113)=1. Это значит, что 661 и 113 – это взаимно простые числа. Мы могли выяснить это до начала вычислений, если бы обратились к таблице простых чисел.
Ответ: НОД(661, 113)=1.
Нахождение НОД с помощью разложения чисел на простые множители
Для того, чтобы найти наибольший общий делитель двух чисел методом разложения на множители, необходимо перемножить все простые множители, которые получаются при разложении этих двух чисел и являются для них общими.
Если мы разложим числа 220 и 600 на простые множители, то получим два произведения: 220=2·2·5·11 и 600=2·2·2·3·5·5. Общими в этих двух произведениях будут множители 2,2 и 5. Это значит, что НОД(220, 600)=2·2·5=20.
Найдите наибольший общий делитель чисел 72 и 96.
Решение
Найдем все простые множители чисел 72 и 96:
72361893122233
96482412631222223
Общими для двух чисел простые множители: 2, 2, 2 и 3. Это значит, что НОД(72, 96)=2·2·2·3=24.
Ответ: НОД(72, 96)=24.
Правило нахождения наибольшего общего делителя двух чисел основано на свойствах наибольшего общего делителя, согласно которому НОД(m·a1, m·b1)=m·НОД(a1, b1), где m– любое целое положительное число.
Нахождение НОД трех и большего количества чисел
Независимо от количества чисел, для которых нам нужно найти НОД, мы будем действовать по одному и тому же алгоритму, который заключается в последовательном нахождении НОД двух чисел. Основан этот алгоритм на применении следующей теоремы: НОД нескольких чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2, НОД(d2, a3)=d3, НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.
Найдите наибольший общий делитель четырех чисел 78, 294, 570 и 36.
Решение
Введем обозначения: a1=78, a2=294, a3=570, a4=36.
Начнем с того, что найдем НОД чисел 78 и 294: d2=НОД(78, 294)=6.
Теперь приступим к нахождению d3=НОД(d2, a3)=НОД(6, 570). Согласно алгоритму Евклида 570=6·95. Это значит, что d3=НОД(6, 570)=6.
Найдем d4=НОД(d3, a4)=НОД(6, 36). 36 делится на 6 без остатка. Это позволяет нам получить d4=НОД(6, 36)=6.
d4=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.
Ответ: НОД(78, 294, 570, 36)=6.
Нахождение НОД отрицательных чисел
Если нам приходится иметь дело с отрицательными числами, то для нахождения наибольшего общего делителя мы можем воспользоваться модулями этих чисел. Мы можем так поступить, зная свойство чисел с противоположными знаками: числа n и -n имеют одинаковые делители.
Найдите НОД отрицательных целых чисел −231 и −140.
Решение
Для выполнения вычислений возьмем модули чисел, данных в условии. Это будут числа 231 и 140. Запишем это кратко: НОД(−231, −140)=НОД(231, 140). Теперь применим алгоритм Евклида для нахождения простых множителей двух чисел: 231=140·1+91; 140=91·1+49; 91=49·1+42; 49=42·1+7 и 42=7·6. Получаем, что НОД(231, 140)=7.
А так как НОД(−231, −140)=НОД(231, 140), то НОД чисел −231 и −140 равен 7.
Ответ: НОД(−231, −140)=7.
Определите НОД трех чисел −585, 81 и −189.
Решение
Заменим отрицательные числа в приведенном перечне на их абсолютные величины, получим НОД(−585, 81, −189)=НОД(585, 81, 189). Затем разложим все данные числа на простые множители: 585=3·3·5·13, 81=3·3·3·3 и 189=3·3·3·7. Общими для трех чисел являются простые множители 3 и 3. Получается , что НОД(585, 81, 189)=НОД(−585, 81, −189)=9.
Ответ: НОД(−585, 81, −189)=9.
Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта
#хакнем_математика 👈 рубрика, содержащая интересный, познавательный контент по математике как для школьников, так и для взрослых 🥳
Цикл статей “Дроби”
Первая часть Вторая часть Третья часть
Четвертая часть Пятая часть Шестая часть Седьмая часть Восьмая часть
Здравствуйте, уважаемые читатели!
Предлагаю рассмотреть ещё один способ нахождения Наибольшего Общего Делителя (НОД) двух чисел, известный под названием «АЛГОРИТМ ЕВКЛИДА», использование которого в случаях многозначных чисел часто оказывается значительно рациональнее традиционного способа с разложением чисел на простые множители.
Для начала опишем последовательность шагов алгоритма.
На первом шаге необходимо провести деление бОльшего числа на мЕньшее. Если деление удалось, т.е. остаток оказался равен нулю, то меньшее число и будет Наибольшим Общим Делителем этих двух чисел. В случае ненулевого остатка необходимо продолжить выполнение алгоритма.
На втором шаге необходимо разделить мЕньшее из двух данных чисел (первый делитель) на полученный в первом делении остаток. Если при этом делении получится нулевой остаток, то НОД двух данных чисел равен остатку от деления на первом шаге или, что то же, делителю на втором шаге. В случае ненулевого остатка следует продолжить выполнение алгоритма.
На третьем шаге следует разделить предыдущий делитель (остаток от предпоследнего деления) на остаток, полученный на предыдущем шаге. В случае получения нулевого остатка НОД будет равен остатку, полученному на предыдущем шаге или, что тоже, последнему делителю. В случае получения ненулевого остатка повторять действия на этом шаге вплоть до получения нулевого остатка — в этом случае последний ненулевой остаток или, что то же, последний делитель и будет Наибольшим Общим Делителем.
Замечу, что описание Алгоритма Евклида для нахождения НОД двух натуральных чисел значительно «объёмнее» его исполнения. Найдём, например, НОД (1729; 2584) сначала с использованием традиционного метода с разложением чисел на простые множители, а затем с помощью алгоритма Евклида.
Чтобы реально оценить преимущество алгоритма Евклида, рекомендую самостоятельно проделать разложение этих чисел на простые множители и все остальные операции по нахождению НОД данных чисел этим способом.
А теперь используем алгоритм:
ОТВЕТ: НОД (1729; 2584) = 19.
В заключение отмечу, что алгоритм Евклида тем эффективнее (в сравнении с традиционным), чем больше числа, НОД которых следует найти.
Автор: #себихов_александр 71 год, много лет проработал конструктором-технологом микроэлектронных приборов и узлов в одном из НИИ г. Саратова, затем преподавателем математики и физики.
Читайте наш канал в телеграм – по этой ссылке
Другие статьи автора:
Цикл статей “Дроби”
1 статья 2 статья 3 статья 4 статья 5 статья 6 статья
7 статья 8 статья 9 статья [Текущая]
Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 12 и 8, наибольшим общим делителем будет 4.
Как найти НОД?
Способов найти НОД несколько. Мы рассмотрим один из часто используемых в математике — это нахождение НОД при помощи разложения чисел на простые множители. В общем случае алгоритм будет выглядеть следующим образом:
- разложить оба числа на простые множители (подробнее о разложении чисел на простые множители смотрите тут);
- выбрать одинаковые множители, входящие в оба разложения;
- найти их произведение.
Примеры нахождения наибольшего общего делителя
Рассмотрим приведенный алгоритм на конкретных примерах:
Пример 1: найти НОД 12 и 8
1. Раскладываем 12 и 8 на простые множители:
2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 2 и 2
3. Перемножаем эти множители и получаем: 2 · 2 = 4
Ответ: НОД (8; 12) = 2 · 2 = 4.
Пример 2: найти НОД 75 и 150
Этот пример, как и предыдущий с легкостью можно высчитать в уме и вывести ответ 75, но для лучшего понимания работы алгоритма, проделаем все шаги:
1. Раскладываем 75 и 150 на простые множители:
2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 3, 5 и 5
3. Перемножаем эти множители и получаем: 3 · 5 · 5 = 75
Ответ: НОД (75; 150) = 3 · 5 · 5 = 75.
Частный случай или взаимно простые числа
Нередко встречаются ситуации, когда оба числа взаимно простые, т.е. общий делитель равен единице. В этом случае, алгоритм будет выглядеть следующим образом:
Пример 3: найти НОД 9 и 5
1. Раскладываем 5 и 9 на простые множители:
Видим, что одинаковых множителей нет, а значит, что это частный случай (взаимно простые числа). Общий делитель — единица.
Как найти НОД
- Нахождение путём разложения на множители
- Алгоритм Евклида
Рассмотрим два способа нахождения наибольшего общего делителя.
Нахождение путём разложения на множители
Первый способ заключается в нахождении наибольшего общего делителя путём разложения данных чисел на простые множители.
Чтобы найти НОД нескольких чисел, достаточно, разложить их на простые множители и перемножить между собой те из них, которые являются общими для всех данных чисел.
Пример 1. Найти НОД (84, 90).
Решение: Раскладываем числа 84 и 90 на простые множители:
Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой:
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.
В остальных случаях, чтобы найти наибольший общий делитель двух чисел используется следующий порядок действий:
- Из двух данных чисел большее число делят на меньшее.
- Затем, меньшее число делят на остаток, получившийся от деления большего числа на меньшее.
- Далее, первый остаток делят на второй остаток, который получился от деления меньшего числа на первый остаток.
- Второй остаток делят на третий, который получился от деления первого остатка на второй и т. д.
- Таким образом деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель как раз и будет наибольшим общим делителем.
Пример 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.
Последовательное деление так же можно записывать столбиком:
Чтобы найти наибольший общий делитель трёх и более данных чисел, используем следующий порядок действий:
- Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
- Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
- Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.
Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа — 48:
48 : 4 = 12
48 делится на 4 без остатка. Таким образом:
НОД (140, 96, 48) = 4.
Запомните!
Если натуральное число делится только на 1 и на само себя, то оно называется простым.
Любое натуральное число всегда делится на 1 и на само себя.
Число 2 — наименьшее простое число. Это единственное чётное простое число, остальные простые числа — нечётные.
Простых чисел много, и первое среди них — число 2. Однако нет последнего простого числа. В
разделе «Для учёбы»
вы можете скачать таблицу простых чисел до 997.
Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.
Например:
- число 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» — это наибольшее число, на которое оба
числа «a» и
«b» делятся без остатка.
Кратко наибольший общий делитель чисел «a» и «b» записывают так:
НОД (a; b).
Пример: НОД (12; 36) = 12.
Делители чисел в записи решения обозначают большой буквой «Д».
Пример.
Д (7) = {1, 7}
Д (9) = {1, 9}
НОД (7; 9) = 1
Числа
7 и 9 имеют
только один общий делитель — число 1.
Такие числа называют взаимно простыми числами.
Запомните!
Взаимно простые числа — это натуральные числа, которые имеют только
один общий делитель — число 1. Их НОД
равен 1.
Как найти наибольший общий делитель
Чтобы найти НОД двух или более натуральных чисел нужно:
- разложить делители чисел на простые множители;
Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое,
справа — делитель. Далее в левом столбце записываем значения частных.
Поясним сразу на примере. Разложим на простые множители числа 28 и 64.
- Подчёркиваем одинаковые простые множители в обоих числах.
28 = 2 · 2 · 764 = 2 · 2 · 2 · 2 · 2 · 2
- Находим произведение одинаковых простых множителей и записать ответ;
НОД (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}
НОД (10; 15) = 5
Ваши комментарии
Важно!
Чтобы оставить комментарий, вам нужно войти на наш сайт при помощи
«ВКонтакте».
Оставить комментарий:
15 ноября 2016 в 17:18
Олеся Ткаченко
Профиль
Благодарили: 0
Сообщений: 1
Олеся Ткаченко
Профиль
Благодарили: 0
Сообщений: 1
Как найти нод чисел
и
???
0
Спасибо
Ответить
15 ноября 2016 в 21:01
Ответ для Олеся Ткаченко
Антон Ершов
Профиль
Благодарили: 0
Сообщений: 2
Антон Ершов
Профиль
Благодарили: 0
Сообщений: 2
0
Спасибо
Ответить
17 ноября 2016 в 10:07
Ответ для Олеся Ткаченко
Евгений Колосов
Профиль
Благодарили: 12
Сообщений: 197
Евгений Колосов
Профиль
Благодарили: 12
Сообщений: 197
Если интересно, есть урок на эту тему.
0
Спасибо
Ответить
12 октября 2015 в 17:28
Илья Ткачёв
Профиль
Благодарили: 0
Сообщений: 1
Илья Ткачёв
Профиль
Благодарили: 0
Сообщений: 1
НОК чисел 12 6 4 и объяснить как ты это сделал! 😀
0
Спасибо
Ответить
1 июля 2016 в 17:09
Ответ для Илья Ткачёв
Евгений Колосов
Профиль
Благодарили: 12
Сообщений: 197
Евгений Колосов
Профиль
Благодарили: 12
Сообщений: 197
Методика подробно и понятно изложена вот на этой странице http://math-prosto.ru/index.php?page=pages/find_nod_and_nok/find_nod.php
А ответ к твоей задаче можно получить в супер решателе на сайте: http://math-prosto.ru/index.php?page=pages/calculators/find_nok_online.php
И он 12 =) Удачи и учитесь пользоваться поиском =)
0
Спасибо
Ответить
2 октября 2015 в 17:37
Булат Махмудов
Профиль
Благодарили: 0
Сообщений: 1
Булат Махмудов
Профиль
Благодарили: 0
Сообщений: 1
Как найти НОК двух чисел если известно их произведение и НОД
0
Спасибо
Ответить
9 июня 2016 в 14:26
Ответ для Булат Махмудов
Евгений Фёдоров
Профиль
Благодарили: 0
Сообщений: 60
Евгений Фёдоров
Профиль
Благодарили: 0
Сообщений: 60
a · b = НОД(a; b) · НОК(a; b)
0
Спасибо
Ответить
21 сентября 2015 в 22:37
Angelina Vorontsovskaya
Профиль
Благодарили: 0
Сообщений: 1
Angelina Vorontsovskaya
Профиль
Благодарили: 0
Сообщений: 1
27=3,3,3. 36=3,3,3.
Наименьшее общее кратное — ?
0
Спасибо
Ответить
22 сентября 2015 в 19:32
Ответ для Angelina Vorontsovskaya
Ольга Морозова
Профиль
Благодарили: 0
Сообщений: 1
Ольга Морозова
Профиль
Благодарили: 0
Сообщений: 1
27=3,3,3
36=2,2,3,3
НОК=3 · 3=9
0
Спасибо
Ответить
6 мая 2015 в 9:20
Сергей Михель
Профиль
Благодарили: 0
Сообщений: 1
Сергей Михель
Профиль
Благодарили: 0
Сообщений: 1
Часиное двух чисел равно наибольшему общему делителю чисел 12 и 16.Сумма этих чисел равна наименьшему общему кратному чисел 50 и 75. Найдите эти числа
0
Спасибо
Ответить
16 апреля 2016 в 8:49
Ответ для Сергей Михель
Евгений Колосов
Профиль
Благодарили: 12
Сообщений: 197
Евгений Колосов
Профиль
Благодарили: 12
Сообщений: 197
Вот тут можно найти объяснение темы НОД и НОК : http://math-prosto.ru/index.php?page=pages/find_nod_and_nok/find_nod.php
А вот тут можно найти математический кальклятор: http://math-prosto.ru/index.php?page=pages/calculators/calculators.php
Решение:
Найдём НОД чисел 12 и 16. Это число 4
Найдём НОК чисел 50 и 75. Это число 150
Обозначим искомые числа как Х и Y и составим уравнения:
x: y=4
x + y=150
x=150-y
150-y: y = 4
y?0
150-y=4y
5y=150
y=30
x=150-30
x=120
Проверка:
120:30=4
4=4
120+30=150
150=150
Ответ: эти числа 120 и 30
0
Спасибо
Ответить
