Нахождение нод трех и большего количества чисел. Наибольший общий делитель (НОД) – определение, примеры и свойства Простой способ нахождения нод
Делимое, которое делится на данный делитель без остатка, иначе называют кратным . Например, 48 кратно 8, число 48 - кратное, число 8 - делитель.
Число может быть кратно не одному, а сразу нескольким числам, такое число называют общим кратным . Например, число 77 общее кратное чисел: 1, 7, 11, 77.
Ещё пример. Числу 3 кратны числа 12, 15 , 24, 27, 30 и т. д. Числу 5 кратны числа 10, 15 , 25, 30 , 35 и т. д. Числа 3 и 5 имеют общие кратные 15 и 30.
Найти общее кратное нескольких чисел довольно просто, можно просто перемножить данные числа, в результате, произведение этих чисел и будет их общим кратным.
НОК
Из всех общих кратных для данных чисел, особый интерес представляет наименьшее общее кратное.
Наименьшим общим кратным (сокращённо НОК) нескольких данных чисел называется самое маленькое число, которое делится нацело на каждое из данных чисел.
Например, для трёх чисел: 3, 5 и 12 наименьшим общим кратным является число 60, так как никакое другое число меньше 60 не делится нацело на 3, на 5 и на 12.
Обычно наименьшее общее кратное записывают так: НОК (a , b , ...) = x .
Согласно этому, запишем наименьшее общее кратное чисел 3, 5 и 12:
НОК (3, 5, 12) = 60.
Калькулятор НОК
Данный калькулятор поможет вам найти наименьшее общее кратное чисел. Просто введите числа через пробел или запятую и нажмите кнопку Вычислить НОК.
Делитель - это целое число, на которое другое целое число делится без остатка. Для нескольких чисел можно найти общие делители, среди которых будет наибольший. Именно наибольший общий делитель обладает рядом полезных свойств.
Наибольший общий делитель
Делитель целого числа 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 классе.
Наибольший общий делитель. НОД.
Для нахождения общего делителя вам нужно знать следующее:
Запомните: наибольший общий делитель (НОД) двух целых чисел – это наибольшее целое число, на которое делятся оба исходных числа без остатка. Однако одно из исходных чисел должно быть большее нуля.
Запомните: если у вас одно из двух чисел ноль, то НОД будет, то число что больше ноля.
Запомните: существует понятие взаимно-простых чисел, у которого нет общих делителей, кроме единицы. К примеру число 5 и 4, НОД этих чисел будет равен 1, так как если 5 разделить на 4 вы не получите целое число без остатка, следовательно НОД=1
Все остальные числа, у которых НОД больше 1, вычисляются по принципу бинарного алгоритма или с помощью алгоритма Евклида. В этой статье мы подробно разберем алгоритм Евклида, который еще называют взаимным вычитанием, поскольку НОД получается при последовательном вычитании меньшего из большего. Используем алгоритм Евклида в нашем примере НОД(12, 30). По алгоритму Евклида нам надо вычесть из большее меньшее, то есть из 30-12-12=6 В числе 30 у нас может поместиться число 12 только два раза, число 12 называют кратным, и остатком останется число 6. Теперь нам надо из числа 30 отнять кратное числа 6, которое у нас получилось, 30-6-6-6-6-6=5 НОД числа 12 и 30 будет равен 6. Так как нам надо найти именно наибольший делитель в нашем случаи 6 больше 5, следовательно НОД(12,30)=6. Как видите ничего сложного, теперь давайте составим блок схему.
Блок-схема «Алгоритм Евклида»
рис.1
Если число a и b равно, НОД этих чисел будет любое из них, так как они могут делиться друг на друга. Если a и b не равны, мы их сравниваем a, если a меньше чем b то их надо поменять местами в a присвоить значение b, в b присвоить значение а и перейти к следующему вычислению описанного ниже. Если a больше чем b то, надо из а вычесть b , результат сохранить в a , и так до тех пор, пока а не станет равно b . Рассмотрим на примере.
Пример НОД(12,30).
- 12=30 | a==b; //в нашем случаи 12 не равно 30
- 12<30 | a
- 30 12 | a==b; b==a; //меняем местами
- 30-12=18 | a=a-b;//производим вычитание
- 18=12| a==b;//равно ли а и b
- 18<12| a
- 18-12=6|a=a-b; //производим вычитание
- 6=12|a==b; //в нашем случаи 6 не равно 12
- 6<12|a
- 6 12| a==b; b==a; //меняем местами
- 12-6=6|a=a-b;//производим вычитание
- 6=6| a==b; //в нашем случаи 6 равно 6
- НОД(12,30)=6;
Наименьшее общее кратное(НОК).
НОК-это число которое из двух и более натуральных чисел является наименьшим натуральным числом, которое само делится нацело, и каждое из исходных чисел.
Самый простой и быстрый способ в плане реализации программного кода, это первоначально вычислить НОД двух чисел, затем произведение исходных двух целых чисел a и b разделить на НОД. Посмотрим на примере как это выглядет. Возьмем за пример все те же цифры 12 и 30 как мы помним наибольшее общее кратное равнялось 6. НОД=6 Следовательно по формуле НОК=a*b/НОД. НОК=12*30/6=60 Есть и другие варианты вычисления НОК к примеру каноническое разложение чисел. Рассмотрим пример, первоначально нам надо выяснить какое из чисел больше, потом мы раскладываем числа на кратные 12= 2 *2* 3 , и число 30= 2 * 3 *5 Вычисляем произведение кратных чисел из числа 30, так как оно является наибольшим. В следующей операции, одинаковые цифры вычеркиваются, как это сделал я из большего меньшее, а оставшиеся кратные числа из 12 умножаются друг на друга, у нас осталось только число 2, которое умножается на произведение кратных чисел из 30, в результате вычисления вы и получите НОК. Выглядет это следующим образом НОК=2*3*5*2=60 Хорошо это можно представить в виде столбиков, как это можно видеть из рис. 2.
рис. 2
В целом ничего сложного, главное не запутаться, сейчас мы нарисуем блок схему наименьшего общего кратного (НОК).
Блок схема Наименьшего общего кратного (НОК)
рис 3.
Алгоритм работы программы описан вначале, статьи о НОК.
Но как же быть если нам надо к примеру найти НОД трех и более натуральных чисел, или найти НОК трех или более натуральных чисел. Тут ничего сложного инструкцию по нахождению НОД из 3 чисел и НОК смотрим ниже.
НОД трех чисел:
- Сравниваем все числа К примеру a
- Начинаем вычисления с больших чисел к меньшим
- Вычисляем НОД по аналогии с двумя числами a и b
- Вычисляем по аналогии чисел НОД(a,b) и с Пример: НОД(a,b,c)=НОД((НОД(a,b)),с);
- НОД(12,30,60)
- 12<30<60
- НОД(60,30)=30
- НОД(30,12)=6
Точно так же производиться вычисления НОД из четырех чисел из пяти итд. По аналогии с НОД вычисляется и НОК с тремя и более числами. Приведу в пример НОД трех чисел блок схему алгоритма смотрите рис. 4.
Блок схема НОД алгоритма трех чисел, четырех чисел итд.
рис. 4
Разберем по подробнее работу программы блок схемы из рис. 4.
- У нас подается 3 числа, но их может быть сколько угодно.
- Их мы записываем в массив array.
- Выполняем метод sort(); Это мой метод он принимает массив чисел, делает сортировку по убыванию, пузырьковым методом, о нем вы можете прочитать из уроков о массивах.
- Выполняем метод nod(), который принимает первые два числа. Я создал метод по аналогии как написано выше в этой статье.
- В следующем блоке я помещаю в тело цикла метод nod(), который присваиваю возвращаемое число из метода nod() переменной a.
- Выводим результат.
- Завершаем работу программы.
.
Пока писал статью, написал программу НОК и НОД вычисления, которую можете скачать с сайта. Работа программы очень простая, достаточно в текстовое поле вписать цифры через пробел или запятую, нажать на кнопку вычислить или Enter и программа выведет результат. Программа написана на языке java. Может запускаться со всех систем.
рис 5.
Скачать калькулятор НОК и НОД .
Запомните!
Если натуральное число делится только на 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
Оформить нахождение НОД можно двумя способами: в столбик (как делали выше) или «в строчку».
Рассмотрим два способа нахождения наибольшего общего делителя.
Нахождение путём разложения на множители
Первый способ заключается в нахождении наибольшего общего делителя путём разложения данных чисел на простые множители.
Чтобы найти НОД нескольких чисел, достаточно, разложить их на простые множители и перемножить между собой те из них, которые являются общими для всех данных чисел.
Пример 1. Найдём НОД (84, 90).
Раскладываем числа 84 и 90 на простые множители:
Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой: 1 · 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 - это значит, что НОД (140, 96) = 4.
Последовательное деление так же можно записывать столбиком:
Чтобы найти наибольший общий делитель трёх и более данных чисел, используем следующий порядок действий:
- Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
- Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
- Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.
Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа - 48:
48 делится на 4 без остатка. Таким образом, НОД (140, 96, 48) = 4.
Загрузка...
