Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 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 на простые множители:
Видим, что одинаковых множителей нет, а значит, что это частный случай (взаимно простые числа). Общий делитель — единица.
Наибольший общий делитель
4.3
Средняя оценка: 4.3
Всего получено оценок: 223.
4.3
Средняя оценка: 4.3
Всего получено оценок: 223.
Наибольший общий делитель – это еще один показатель, позволяющий упростить работу с дробями. Очень часто в результате вычислений получаются дроби с очень большими значениями числителя и знаменателя. Сокращать поэтапно такие числа можно, но это крайне долго, поэтому проще сразу найти НОД и сократить на него. Разберемся в теме подробнее.
Что такое НОД?
Наибольший общий делитель (НОД) ряда чисел – это наибольшее число, на которое можно без остатка разделить каждое из чисел ряда.
Это значение чаще всего используется для ряда из двух чисел. Просто потому, что сокращаются обычно два числа: числитель и знаменатель дроби. Нахождение НОД для большего количества значений не всегда оправдано, но вырабатывает навык.
Как найти НОД?
Для того, чтобы найти НОД необходимо каждое из чисел разложить на простые множители и выделить общую часть.
Специальной формулы для этого не придумали, зато есть алгоритм вычисления.
Приведем пример нахождения наибольшего общего делителя двух натуральных чисел: 540 и 252. Разложим 640 на простые множители. Последовательность действий такова:
- Делим число на наименьший из возможных простых чисел. То есть, если число можно разделить на 2, 3 или 5, то сначала нужно делить на 5. Просто, чтобы не запутаться.
- Получившийся результат делим на наименьшее из возможных простых чисел.
- Повторяем деление каждого полученного результата, пока не получим простое число.
Теперь проведем ту же процедуру на практике.
- 540 : 2=270
- 270:2=135
- 135 : 3 =45
- 45 : 3=15
- 15 : 5 = 3
Запишем результат в виде равенства 540=2*2*3*3*3*5. Для того, чтобы записать результат, нужно последнее получившееся число умножить на все делители.
Аналогично поступим с числом 252:
- 252 : 2=126
- 126: 2=63
- 63 : 3=21
- 21 : 3 = 7
Запишем результат: 252=2*2*3*3*7.
В каждом разложении есть одинаковые числа. Найдем их, это два числа 2 и два числа 3. Отличаются только 7 и 3*5.
Для того, чтобы найти НОД нужно перемножить общие множетели. То есть в произведении будет две двойки и две тройки.
НОД=2*2*3*3=36
Как можно это использовать?
Задача: сократить дробь $$252over540$$.
НОД для двух этих чисел мы уже находили, теперь просто воспользуемся уже посчитанным значением.
НОД = 36
Сократим числитель и знаменатель дроби на 36 и получим ответ.
$${252over540} ={7over15}$$ – чтобы быстро сократить, достаточно посмотреть на разложение чисел.
Если 540=2*2*3*3*3*5, а НОД=36=2*2*3*3, то 540 = 36*3*5. И если мы поделим 540 на 36, то получим 3*5=15.
Без НОД нам пришлось бы в одну длинную строку писать сокращения. К тому же, бывают случаи, когда непонятно, можно ли сократить дробь вообще. Для таких ситуаций в математике и придумали разложение чисел на простые множители и НОД.
Что мы узнали?
Мы узнали, что такое наибольший общий делитель пары чисел, разобрались, как можно использовать показатель на практике, решили задачу на нахождение НОД и применение НОД для сокращения дробей. Поняли, что с использованием НОД можно проще и быстрее сократить громоздкие дроби, найдя НОД для числителя и знаменателя.
Тест по теме
Доска почёта
Чтобы попасть сюда — пройдите тест.
Пока никого нет. Будьте первым!
Оценка статьи
4.3
Средняя оценка: 4.3
Всего получено оценок: 223.
А какая ваша оценка?
Загрузить PDF
Загрузить PDF
Нахождение наибольшего общего делителя (НОД) для определенного количества чисел может быть легкой задачей, если вы умеете это делать.
-
1
Найдите делители чисел. Начните с поиска всех делителей первого и второго числа.
-
2
Сравните делители обоих чисел и найдите самое большое число, которое есть в списке делителей как первого, так и второго числа. Это число равно НОД.
Реклама
-
1
Разложите каждое число на простые множители. Простое число — это число, большее 1 и которое делится только на 1 и на само себя. Примеры простых чисел: 5, 17, 97, 331.
-
2
Найдите общие простые множители. Общий простой множитель может быть только один, или их может быть несколько.
-
3
Если у двух чисел есть только один общий простой множитель, то он равен НОД. Если у двух чисел есть несколько общих простых множителей, то их произведение равно НОД.
-
4
Изучите пример. Чтобы продемонстрировать этот метод, изучите пример, приведенный на рисунке.
Реклама
Советы
- Простое число — это число, которое делится только на 1 и на само себя.
- Знаете ли вы, что в третьем веке до н.э. математик Евклид создал алгоритм для вычисления наибольшего общего делителя двух натуральных чисел и двух многочленов?
Реклама
Об этой статье
Эту страницу просматривали 7409 раз.
Была ли эта статья полезной?
Как найти НОД двух чисел по алгоритму Евклида
Содержание:
- Что такое алгоритм Евклида
- Понятие НОД
-
Основная суть алгоритма Евклида
- Последовательность нахождения НОД при помощи деления:
- Последовательность нахождения НОД при помощи вычитания:
- Примеры решения задач с алгоритмом Евклида
Что такое алгоритм Евклида
Алгоритм Евклида — один из наиболее ранних численных алгоритмов в истории. Название было дано в честь греческого математика Евклида, который впервые дал ему описание в книгах «Начала». Изначально назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль. Сегодня чаще используется взятие остатка от деления вместо вычитания, но суть метода сохранилась.
Алгоритм Евклида — это алгоритм, основная функция которого заключается в поиске наибольшего общего делителя (НОД) для двух целых чисел.
Простейшим случаем применения данного алгоритма является поиск наибольшего общего делителя для пары положительных целых чисел. Евклид, автор этого метода, предполагал его использование только для натуральных чисел и геометрических величин. Но позже алгоритм был обобщен и для других групп математических объектов, что привело к появлению такого понятия, как евклидово кольцо.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
Понятие НОД
Аббревиатура НОД расшифровывается как «наибольший общий делитель».
Наибольший общий делитель — делитель, который делит без остатка два числа, при этом сам делится без остатка на любой другой делитель исходных двух чисел. То есть это самое большое число, на которое без остатка можно разделить пару чисел, для которых подбирается НОД.
Основная суть алгоритма Евклида
Суть алгоритма заключается в построении ряда следующего вида (при условии, что a больше b):
a, b, x1, x2, x3, … xn.
В нем каждое последующее число — это остаток от деления двух предыдущих, ряд заканчивается, когда остаток от деления становится равным 0 — при условии использования деления.
В нем каждое последующее число является результатом вычитания двух предыдущих, ряд заканчивается, когда частное становится равным 0 — при условии использования вычитания.
Последовательность нахождения НОД при помощи деления:
- Большее число делится на меньшее.
- Если результат деления:
- без остатка, то меньшее число и есть НОД;
- с остатком, тогда большее число заменяется на остаток.
- Переход к пункту 1.
Пример №1
60 / 36 = 1 (остаток 24)
36 / 24 = 1 (остаток 12)
24 / 12 = 2 (остаток 0)
НОД для 60 и 36 равен 12 (делитель).
Последовательность нахождения НОД при помощи вычитания:
- Из большего числа вычитается меньшее.
- Если результат вычитания:
- равен 0, то числа равны друг другу и являются НОД;
- не равен 0, в таком случае большее число заменяется на результат вычитания.
- Переход к пункту 1.
Пример №2
60 — 36 = 24
36 — 24 = 12
24 — 12 = 12
12 — 12 = 0
НОД для 60 и 36 равен 12 (уменьшаемое, вычитаемое)
Примеры решения задач с алгоритмом Евклида
Задача №1
Найти наибольший общий делитель для чисел 128 и 96.
Решение:
128 — 96 = 32
96 — 32 = 64
64 — 32 = 32
32 — 32 = 0
Или
128 / 96 = 1 (остаток 32)
96 / 32 = 3
Ответ: 32
Задача №2
Найти наибольший общий делитель для чисел 37 и 17.
Решение:
37 / 17 = 2 (остаток 3)
17 / 3 = 5 (остаток 2)
3 / 2 = 1 (остаток 1)
2 / 1 = 2 (остаток 0)
Или
37 — 17= 20
20 — 17 = 3
17 — 3 = 14
14 — 3 = 11
11 — 3 = 8
8 — 3 = 5
5 — 3 = 2
3 — 2 = 1
2 — 1 = 1
1 — 1 = 0
Числа 37 и 17 являются простыми, соответственно, их НОД — единица. Совет: перед вычислениями проверяйте таблицу простых чисел.
Ответ: 1
Насколько полезной была для вас статья?
Рейтинг: 4.50 (Голосов: 18)
Выделите текст и нажмите одновременно клавиши «Ctrl» и «Enter»
Текст с ошибкой:
Расскажите, что не так