Калькулятор НОД

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

Термин НОД

НОД – это наибольшее общее делимое, каких-либо чисел, которое кратно обеим числам без остатка в ответе. Если НОД равен единице, то такие числа называются взаимно простыми.

Перед более подробным разъяснением темы, стоит вспомнить ряд других терминов. Для начала вспомним, что такое делитель, это целое число, кратное на заданное число так, чтобы в ответе не было остатка.

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

Рассмотрим мы с вами это понятие на примере. Будет лучше раскрыть термин через пример. Допустим, у нас есть два числа, например, это будут числа 120 и 140. Для начала стоит напомнить, что такое делители числа. Делители – это те числа, которые делят числа нацело.

Запишем делители 120 и 140. Не требуется выписывать все делители этих чисел и именно в том порядке, в котором они идут, нескольких будет вполне достаточно. Запишем делители числа (не все) числа 120:

• 1;
• 2;
• 3;
• 4;
• 5;
• 6;
• 10;
• 20 и т.д.

Точно также запишем делители числа 140:

• 1;
• 2;
• 4;
• 5;
• 7;
• 10;
• 20.

Заметим, что некоторые делители повторяются: 1, 2, 4, 5, 10, 20. Они будут общими делителями 120 и 140. Из этих всех чисел можно выбрать наибольшее, а именно 20. Можно сказать, что это самое большое натуральное число, будучи делителем, как и 120, так и 140. То есть это и есть их НОД. НОД более 2-ух чисел будет наибольшее число, кратное на все заданные числа без остатка.

Что умеет калькулятор НОД

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

Во время использования онлайн-калькулятора не возникает трудностей, он прост в использовании. Достаточно просто ввести несколько чисел через запятую и нажать на кнопку «Рассчитать». Если вам необходимо ввести другие данные в онлайн-калькулятор – требуется просто нажать на кнопку «Сбросить».

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

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

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

Методы вычисления НОД

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

Метод разложения на простые множители

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

Пример №1

Найдем НОД (12;20). Первым делом выполним разложение на простые множители. Разложим на простые множители число 12. Простые множители лучше располагать в порядке возрастания, чтобы было удобнее, и мы не запутались 12 мы можем разделить на 2, в ответе получаем 6. 6 тоже делится на 2, будет 3. 3 – простое число, его делим самого на себя, в ответе получаем конечную единицу.

Теперь разложим 20. 20 также делится на 2, в ответе получаем 10. 10 делим на 2, в ответе 5. 5 – простое число, делим его самого на себя, получаем единицу. Помним, что мы их раскладывали не только на простые множители, нам нужны общие делители. Ищем общие множители у 12 и 20. Видим, что из общих множителей у чисел только по две двойки, сразу обводим эти числа. Затем выписываем следующее выражение: 2 * 2, считаем, в ответе получаем 4 – это и будет НОД (12; 20).

Пример №2

Найдем НОД (30; 5). Начинаем разложение, для начала разложим число 30. 30 делится на 2, в ответе получаем 15. 15 делится на 3, в ответе 5. Как мы уже знаем, 5 – простое число. Делим его самого на себя, в ответе 1. У 30 следующие простые множители:

• 2;
• 3;
• 5.

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

Алгоритм Евклида

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

Если не совсем понятно, запишем алгоритм Евклида в виде форм. Оказывается, НОД (m и n) (если m больше n) будет равен НОД (m – n; n). Вот это и есть в первоначальном самом простом виде алгоритм Евклида для нахождения НОД (m и n). То есть, мы пару чисел m и n можем заменить на разность этих двух чисел (из большего вычитаем меньшее) и меньшего числа.

Чтобы понять и доказать алгоритм Евклида достаточно проверить следующие два утверждения. Первое утверждение такое. Все общие делители первой пары (m и n) совпадают с общими делителями второй пары (m – n; n). И общие делители второй пары (m – n; n) совпадают с общими делителями первой (m и n). Потому что, если общие делители первой и второй пары совпадают, значит и наибольшее общее кратное у них совпадает.

Как же это доказать? Предположим, что мы имеем число k, которое является общим делителем чисел m и n, то есть первой пары. Но тогда, если число m и n делятся на k без остатка, то тогда на число k делится разность (m и n) и само число n. Ведь если число k является делителем чисел m и n, то естественно данная разность, если уменьшаемое и вычитаемое делится на число k, значит и разность делится на число k. Само число n также делится на k. То есть мы получаем, что делители первой пары совпадают с делителями второй пары.

Теперь рассмотрим делители второй пары (m – n; n). Если число к является общим делителем вот этого числа (m – n; n), то тогда число k является общим делителем (m и n). Потому что если число m – n и число n делятся на k без остатка, то тогда и число m будет кратно k без остатка. Теперь мы и получаем, что общий делитель второй пары (m – n; n) совпадает с общим делителем первой пары (m и n). Это значит, что и НОД будет совпадать. Теперь разберем несколько примеров.

Пример №1

Предположим нам необходимо найти НОД (36;48). Если находить НОД при помощи разложения, то получим 12, проверим, будет ли так при решении алгоритмом Евклида. С помощью алгоритма Евклида мы можем заменить данную пару чисел на меньшее из них – 36. То есть 36 оставляем. А в качестве второго будет разность большего и меньшего числа, то есть 48 – 36. В итоге у нас получается НОД (36; 12). Отсюда уже видно, что 12 делится нацело на 36. А это значит, что 12 – НОД. В итоге у нас получились следующие записи:

НОД (36; 48) = НОД (36, 48-36) = НОД (36; 12) = 12.

Мы можем оставить все так, а можем продолжить решение. Продолжаем процедуру. Оставляем в скобках только наименьшее число, а именно 12 и вычитаем из большего меньшее, записываем: НОД (12; 36 – 12) = НОД (12; 24) = НОД (12; 24 – 12) = НОД (12, 12) = 12. Вот и алгоритм Евклида в действии.

Пример №2

Найдем НОД чисел (56; 14). Заменим пару чисел. Выписываем в скобочки наименьшее число, а именно 14. Далее выписываем разность 56 и 14. Получаем следующие записи: НОД (56; 14) = НОД (14; 56 – 14) = НОД (14; 42). Продолжим решение, получаем следующие выражения: НОД (14; 42) = НОД (14; 42 – 14) = НОД (14; 28) = НОД (14; 28 – 14) = НОД (14; 14). В ответе мы получаем, что НОД равно 14. Как можно заметить в алгоритме Евклида нет ничего сложного, и он просто для понимания.

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

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

Найдем НОД (84; 189; 315). Для начала каждое из этих чисел разложим на простые множители. Разложим число 84. Оно четное – делим на 2, разделив на 2, получаем 42. 42 тоже четное число, делим на 2, получаем 21. 21 делится на 3, получаем 7. 7 – простое число, делим его самого на себя, в ответе получаем единицу. У 84 мы получаем следующие множители:

• 2;
• 2;
• 3;
• 7.

Далее раскладываем число 189. На 2 оно не разделится. Складываем цифры числа 189, получаем 18, 18 делится на 3, поэтому разделим 189 на 3, в ответе получаем 63. 63 тоже делится на 3, получаем 21. 21 разделим на 3, получим 7. 7 делим само на себя, получаем единицу. Множители 189:

• 3;
• 3;
• 3;
• 7.

Разложим число 315 на множители. 315 делится на 3, в ответе получаем 105. 105 тоже делится на 3, в результате 35. 35 разделим на 5, получим 7. 7 делим само на себя, получаем единицу. Множители 315:

• 3;
• 3;
• 5;
• 7.

Выберем множители 189 и будем убирать те множители, которых нет у других двух чисел. В итоге мы две тройки из множителей 189. Чтобы получить НОД, умножим 3 на 7, получаем 21, это и будет НОД (84; 189; 315).

Свойства НОД

Теперь мы поняли, как найти НОД двух и более чисел. Теперь стоит обсудить свойства НОД. Всего существует 5 свойств НОД.

1. НОД (m; n) = НОД (n; m);
2. НОД (m; n), m : n = n;
3. НОД (m; n) = НОД (n; b). Где b целое число.
4. НОД (ma; mb) = m * НОД (a; b). Где m – натуральное число.
5. M : НОД (m; n) и n : НОД (m; n) – взаимно простые.