Делитель — это целое число, на которое другое целое число делится без остатка. Для нескольких чисел можно найти общие делители, среди которых будет наибольший. Именно наибольший общий делитель обладает рядом полезных свойств.
Наибольший общий делитель
Делитель целого числа A – это целое число B, на которое A делится без остатка. К примеру, делители числа 24 — 1, 2, 3, 4, 6, 8, 12, 24. Каждое число делится на себя и на единицу, поэтому эти делители мы можем не учитывать. Числа, которые делятся только на себя и единицу, считаются простыми и обладают рядом уникальных свойств. Однако к большинству чисел мы можем подобрать делители, некоторые из которых будут общими. К примеру, для числа 36 такими делителями будут 2, 3, 4, 6, 9, 12, 18. Большинство из них совпадает с делителями числа 24, приведенными выше, но наибольшим из них является 12. Это и есть НОД пары 24 и 36. Понятие наименьшего общего делителя не имеет смысла, так как это всегда единица.
Нахождение НОД
Для вычисления НОД используется три способа. Первый, самый простой для понимания, но при этом наиболее трудоемкий — это простой перебор всех делителей пары и выбор из них наибольшего. Например, для 12 и 16 НОД находится следующим образом:
- выписываем делители для 12 — 2, 3, 4 и 6;
- выписываем делители для 16 — 2, 4 и 8;
- определяем общие делители чисел — 2, 4;
- выбираем наибольший из них — 4.
Второй способ сложнее для понимания, но более эффективен в плане вычислений. В этом случае НОД находится путем разложения чисел на простые множители. Для разложения на простые множители необходимо последовательно делить число без остатка на числа из ряда простых 2, 3, 5, 7, 11, 13…
Для тех же чисел НОД вычисляется по такой схеме:
- раскладываем 12 на простые множители и получаем 2 × 2 × 3;
- раскладываем 16 — 2 × 2 × 2× 2;
- отсеиваем несовпадающие множители и получаем 2 × 2;
- перемножаем множители и определяем НОД = 4.
Третий способ лучше всего подходит для определения НОД пар любых, сколь угодно больших чисел. Алгоритм Евклида — это метод поиска наибольшего общего делителя для пары целых чисел A и B, при условии A>B.
Согласно алгоритму мы должны разделить A на B, в результате которого получится:
A1 и C,
где A1 – целое число, C – остаток от деления.
После этого разделим B на остаток C и обозначим результат как B1. Теперь у нас есть новая пара чисел A1 и B1.
Повторим действия. Разделим A1 на B1, получим в результате A2 и C1. После этого разделим B1 на C1 и получим B2. Алгоритм повторяется до тех пор, пока остаток Cn не будет равен нулю.
Рассмотрим его подробно на числах 1729 и 1001. Порядок действий следующий. У нас есть пара (1001, 1729). Для использования алгоритма Евклида первое число в паре должно быть больше. Выполним преобразование для корректной работы алгоритма — меньшее число оставим на месте, а большее заменим на их разницу, так как если оба числа делятся на НОД, то их разность также делится. Получим (1001, 728). Выполним расчеты:
- (1001, 728) = (728, 273) = (273, 182) — вместо того, чтобы много раз искать разность, можно написать остаток от деления 728 на 273.
- (273, 182) = (91, 182) = (91, 0) = 91.
Таким образом, НОД пары 1001 и 1729 равен 91.
Использование НОД
На практике наибольший общий делитель применяется при решении диофантовых уравнений вида ax + by = d. Если НОД (a, b) не делит d без остатка, то уравнение не разрешимо в целых числах. Таким образом, диофантово уравнение имеет целые корни только в случае, если отношение d / НОД (a, b) есть целое число.
Наш онлайн-калькулятор позволяет быстро отыскать наибольший общий делитель как для пары, так и для любого произвольного количества чисел.
Примеры из реальной жизни
Школьная задача
В задаче по арифметике требуется найти НОД четырех чисел: 21, 49, 56, 343. Для решения при помощи калькулятора нам потребуется только указать количество чисел и ввести их в соответствующие ячейки. После этого мы получим ответ, что НОД (21, 49, 56, 343) = 7.
Диофантово уравнение
Пусть у нас есть диофантово уравнение вида 1001 х + 1729 у = 104650. Нам необходимо проверить его на разрешимость в целых чисел. Мы уже считали НОД для этой пары при помощи алгоритма Евклида. Давайте проверим правильность выкладок и пересчитаем НОД на калькуляторе. Действительно, НОД (1001, 1729) = 91. Проверяем возможность целочисленного решения по условию d / НОД (a, b) = 104650/91 = 1150. Следовательно, данное уравнение имеет целые корни.
Заключение
Наибольший общий делитель мы проходим еще в школе, но не всегда понимаем, для чего он нужен в будущем. Однако НОД — важный термин в теории чисел и применяется во многих областях математики. Используйте наш калькулятор для поиска НОД любого количества чисел.