Формула для нахождения н. Алгоритм евклида - нахождение наибольшего общего делителя. Определение наибольшего общего делителя

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

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

Делитель целого числа 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 – остаток от деления.

После этого разделим 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. Следовательно, данное уравнение имеет целые корни.

Заключение

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

Чтобы понять, как вычислять НОК, следует определиться в первую очередь со значением термина "кратное".

Кратным числу А называют такое натуральное число, которое без остатка делится на А. Так, числами кратными 5 можно считать 15, 20, 25 и так далее.

Делителей конкретного числа может быть ограниченное количество, а вот кратных бесконечное множество.

Общее кратное натуральных чисел - число, которое делится на них без остатка.

Как найти наименьшее общее кратное чисел

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

Чтобы найти НОК, можно использовать несколько способов.

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

Например, кратные числа 4 можно записать так:

К (4) = {8,12, 16, 20, 24, ...}

К (6) = {12, 18, 24, ...}

Так, можно увидеть, что наименьшим общим кратным чисел 4 и 6 является число 24. Эту запись выполняют следующим образом:

НОК (4, 6) = 24

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

Для выполнения задания необходимо разложить предложенные числа на простые множители.

Сначала нужно выписать в строчку разложение наибольшего из чисел, а под ним - остальных.

В разложении каждого числа может присутствовать различное количество множителей.

Например, разложим на простые множители числа 50 и 20.

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

Теперь можно вычислить наименьшее общее кратное 20 и 50.

НОК (20, 50) = 2 * 5 * 5 * 2 = 100

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

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

В качестве примера можно найти наименьшее общее кратное чисел 16, 24, 36.

36 = 2 * 2 * 3 * 3

24 = 2 * 2 * 2 * 3

16 = 2 * 2 * 2 * 2

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

Таким образом, их нужно добавить к разложению большего числа.

НОК (12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9

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

Например, НОК двенадцати и двадцати четырех будет двадцать четыре.

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

Например, НОК (10, 11) = 110.

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

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

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

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

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

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

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

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

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

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

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

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

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

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 .

Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.

Например :

Число 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 записывают так:

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

Делители чисел в записи решения обозначают большой буквой «Д».

Пример:

НОД (7; 9) = 1

Числа 7 и 9 имеют только один общий делитель - число 1. Такие числа называют взаимно простыми чи слами .

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

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

• Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример : для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
• Следствие 1: множество общих делителей m и n совпадает с множеством делителей НОД(m , n ).
• Следствие 2: множество общих кратных m и n совпадает с множеством кратных НОК (m , n ).

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

• Наибольший общий делитель чисел m и n может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:

и поэтому представим в виде линейной комбинации чисел m и n :

Это соотношение называется соотношением Безу , а коэффициенты u и v — коэффициентами Безу . Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД (a 1 , a 2 , … , a n ).

Вычисление наибольшего общего делителя (НОД).

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм . Кроме того, значение НОД (m ,n ) можно легко вычислить, если известно каноническое разложение чисел m и n на простые множители:

где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД (m ,n ) и НОК (m ,n ) выражаются формулами:

Если чисел более двух: , их НОД находится по следующему алгоритму:

— это и есть искомый НОД.

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

Разберем пошагово вычисление наибольшего общего делителя:

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

Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое, справа - делитель. Далее в левом столбце записываем значения частных. Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

2. Подчёркиваем одинаковые простые множители в обоих числах:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Находим произведение одинаковых простых множителей и записываем ответ:

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

Ключевые слова конспекта: Натуральные числа. Арифметические действия над натуральными числами. Делимость натуральных чисел. Простые и составные числа. Разложение натурального числа на простые множители. Признаки делимости на 2, 3, 5, 9, 4, 25, 10, 11. Наибольший общий делитель (НОД), а также наименьшее общее кратное (НОК). Деление с остатком.

Натуральные числа — это числа, которые используются для счета предметов - 1, 2, 3, 4 , … Но число 0 не является натуральным!

Множество натуральных чисел обозначают N . Запись «3 ∈ N» означает, что число три принадлежит множеству натуральных чисел, а запись «0 ∉ N» означает, что число нуль не принадлежит этому множеству.

Десятичная система счисления - позиционная система счисления по основанию 10 .

Арифметические действия над натуральными числами

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

Пусть a, b и c - натуральные числа, тогда

1. СЛОЖЕНИЕ. Слагаемое + Слагаемое = Сумма

Свойства сложения
1. Переместительное а + b = b + а.
2. Сочетательное а + (b + с) = (а + b) + с.
3. а + 0= 0 + а = а.

2. ВЫЧИТАНИЕ. Уменьшаемое — Вычитаемое = Разность

Свойства вычитания
1. Вычитание суммы из числа а — (b + с) = а — b — с.
2. Вычитание числа из суммы (а + b) — с = а + (b — с); (а + b) — с = (а — с) + b.
3. а — 0 = а.
4. а — а = 0.

3. УМНОЖЕНИЕ. Множитель * Множитель = Произведение

Свойства умножения
1. Переместительное а*b = b*а.
2. Сочетательное а*(b*с) = (а*b)*с.
3. 1 * а = а * 1 = а.
4. 0 * а = а * 0 = 0.
5. Распределительное (а + b) * с = ас + bс; (а — b) * с = ас — bс.

4. ДЕЛЕНИЕ. Делимое: Делитель = Частное

Свойства деления
1. а: 1 = а.
2. а: а = 1. Делить на ноль нельзя!
3. 0: а= 0.

Порядок действий

1. Прежде всего действия в скобках.
2. Потом умножение, деление.
3. И только в конце сложение, вычитание.

Делимость натуральных чисел. Простые и составные числа.

Делителем натурального числа а называется натуральное число, на которое а делится без остатка. Число 1 является делителем любого натурального числа.

Натуральное число называется простым , если оно имеет только два делителя: единицу и само это число. Например, числа 2, 3, 11, 23 - простые числа.

Число, имеющее более двух делителей, называется составным . Например, числа 4, 8, 15, 27 - составные числа.

Признак делимости произведения нескольких чисел: если хотя бы один из множителей делится на некоторое число, то и произведение делится на это число. Произведение 24 15 77 делится на 12 , поскольку множитель этого числа 24 делится на 12 .

Признак делимости суммы (разности) чисел: если каждое слагаемое делится на некоторое число, то и вся сумма делится на это число. Если а: b и c: b , то (а + c) : b . А если а: b , а c не делится на b , то a + c не делится на число b .

Если а: c и c: b , то а: b . Исходя из того, что 72: 24 и 24: 12, делаем вывод, что 72: 12.

Представление числа в виде произведения степеней простых чисел называют разложением числа на простые множители .

Основная теорема арифметики : любое натуральное число (кроме 1 ) либо является простым , либо его можно разложить на простые множители только одним способом.

При разложении числа на простые множители используют признаки делимости и применяют запись «столбиком» В таком случае делитель располагается справа от вертикальной черты, а частное записывают под делимым.

Например, задание: разложить на простые множители число 330 . Решение:

Признаки делимости на 2, 5, 3, 9, 10, 4, 25 и 11.

Существуют признаки делимости на 6, 15, 45 и т. д., то есть на числа, произведение которых можно разложить на множители 2, 3, 5, 9 и 10 .

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

Наибольшее натуральное число, на которое делится нацело каждое из двух данных натуральных чисел, называется наибольшим общим делителем этих чисел (НОД ). Например, НОД (10; 25) = 5; а НОД (18; 24) = 6; НОД (7; 21) = 1.

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

Алгоритм нахождения наибольшего общего делителя (НОД)

НОД часто используется в задачах. Например, между учениками одного класса поделили поровну 155 тетрадей и 62 ручки. Сколько учеников в этом классе?

Решение: Нахождение количества учащихся этого класса сводится к нахождению наибольшего общего делителя чисел 155 и 62, поскольку тетради и ручки поделили поровну. 155 = 5 31; 62 = 2 31. НОД (155; 62) = 31 .

Ответ: 31 ученик в классе.

Наименьшее общее кратное

Кратным натурального числа а называется натуральное число, которое делится на а без остатка. Например, число 8 имеет кратные: 8, 16, 24, 32 , … Любое натуральное число имеет бесконечно много кратных.

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

Алгоритм нахождения наименьшего общего кратного (НОК ):

НОК также часто применяется в задачах. Например, два велосипедиста одновременно стартовали по велотреку в одном направлении. Один делает круг за 1 мин, а другой - за 45 с. Через какое наименьшее количество минут после начала движения они встретятся на старте?

Решение: Количество минут, через которое они снова встретятся на старте, должно делиться на 1 мин , а также на 45 с . В 1 мин = 60 с. То есть необходимо найти НОК (45; 60).
45 = 3 2 5;
60 = 2 2 3 5.
НОК (45; 60) = 2 2 3 2 5 = 4 9 5 = 180 .
В результате получается, что велосипедисты встретятся на старте через 180 с = 3 мин.

Ответ: 3 мин.

Деление с остатком

Если натуральное число а не делится нацело на натуральное число b , то можно выполнить деление с остатком . В таком случае полученное частное называется неполным . Справедливо равенство:

а = b n + r,

где а - делимое, b - делитель, n - неполное частное, r - остаток. Например, пусть делимое равно 243 , делитель - 4 , тогда 243: 4 = 60 (остаток 3) . То есть а = 243, b = 4, n = 60, r = 3, тогда 243 = 60 4 + 3 .

Числа, которые делятся на 2 без остатка, называются четными : а = 2n , n ∈ N.

Остальные числа называются нечетными : b = 2n + 1 , n ∈ N.

Это конспект по теме «Натуральные числа. Признаки делимости» . Чтобы продолжить, выберите дальнейшие действия:

• Перейти к следующему конспекту: