Алгоритм поиска нод и нок. Что такое нод
Наибольшим общим делителем (НОД) двух чисел называется наибольшее число, на которое будут делится оба числа без остатка.
Обозначение : НОД(А; В) .
ПРИМЕР . Найдем НОД чисел 4 и 6.
- Число 4 без остатка делится на: 1, 2 и 4.
- Число 6 без остатка делится на: 1, 2, 3 и 6.
- Наибольшим общим делителем чисел 4 и 6 будет число 2.
- НОД(4;6) = 2
Это простой пример. А как быть с большими числами, для которых надо отыскать НОД?
В таких случаях числа раскладываются на простые множители, после чего одинаковые множители в обоих разложениях отмечаются - произведение отмеченных простых множителей и составит НОД.
ПРИМЕР . Найдем НОД чисел 81 и 45.
81 = 3 · 3 · 3 · 3 45 = 3 · 3 · 5 НОД(81;45) = 3 · 3 = 9
В тех случаях, когда у двух чисел нет одинаковых простых множителей, единственным натуральным числом, на которое нацело будут делиться такие числа будет 1. НОД таких чисел = 1. Например: НОД (7;15) = 1.
Что такое НОК
Число А называют кратным числу В, если А делится на В без остатка (нацело). Например, 10 делится нацело на 5, поэтому, 10 кратно 5; 11 не делится нацело на 5, поэтому, 11 не кратно 5.
Наименьшим общим кратным (НОК) двух натуральных чисел называется наименьшее число, кратное этим двум числам.
Обозначение : НОК(А; В) .
Правило отыскания НОК:
- разложить оба числа на простые множители, отметить одинаковые простые множители в обоих разложениях, если таковые имеются;
- произведение всех простых множителей одного из чисел (собственно, само число) и всех не отмеченных множителей другого числа составят НОК.
ПРИМЕР . Найдем НОК чисел 81 и 45.
81 = 3 · 3 · 3 · 3 45 = 3 · 3 · 5 НОК(81;45) = 81 · 5 = 405
405 является наименьшим кратным для чисел 81 и 45: 405/81 = 5; 405/45 = 9.
Если у двух чисел нет одинаковых простых множителей, то НОК для таких чисел будет равен произведению этих чисел.
14 = 2 · 7 15 = 3 · 5 НОК(14;15) = 14 · 15 = 210
Рассмотрим два способа нахождения наибольшего общего делителя.
Нахождение путём разложения на множители
Первый способ заключается в нахождении наибольшего общего делителя путём разложения данных чисел на простые множители.
Чтобы найти НОД нескольких чисел, достаточно, разложить их на простые множители и перемножить между собой те из них, которые являются общими для всех данных чисел.
Пример 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.
Чтобы понять, как вычислять НОК, следует определиться в первую очередь со значением термина "кратное".
Кратным числу А называют такое натуральное число, которое без остатка делится на А. Так, числами кратными 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.
Рассмотрим два основных метода нахождения НОД двумя основными способами: с использованием алгоритма Евклида и путем разложения на простые множители. Применим оба метода для двух, трех и большего количества чисел.
Алгоритм Евклида для нахождения НОД
Алгоритм Евклида позволяет с легкостью вычислить наибольший общий делитель для двух положительных чисел. Формулировки и доказательство алгоритма Евклида мы привели в разделе «Наибольший общий делитель: определитель, примеры».
Суть алгоритма заключается в том, чтобы последовательно проводить деление с остатком, в ходе которого получается ряд равенств вида:
a = b · q 1 + r 1 , 0 < r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
Мы можем закончить деление тогда, когда r k + 1 = 0 , при этом r k = НОД (a , b) .
Пример 1
64 и 48 .
Решение
Введем обозначения: a = 64 , b = 48 .
На основе алгоритма Евклида проведем деление 64 на 48 .
Получим 1 и остаток 16 . Получается, что q 1 = 1 , r 1 = 16 .
Вторым шагом разделим 48 на 16 , получим 3 . То есть q 2 = 3 , а r 2 = 0 . Таким образом число 16 – это наибольший общий делитель для чисел из условия.
Ответ: НОД (64 , 48) = 16 .
Пример 2
Чему равен НОД чисел 111 и 432 ?
Решение
Делим 432 на 111 . Согласно алгоритму Евклида получаем цепочку равенств 432 = 111 · 3 + 99 , 111 = 99 · 1 + 12 , 99 = 12 · 8 + 3 , 12 = 3 · 4 .
Таким образом, наибольший общий делитель чисел 111 и 432 – это 3 .
Ответ: НОД (111 , 432) = 3 .
Пример 3
Найдите наибольший общий делитель чисел 661 и 113 .
Решение
Проведем последовательно деление чисел и получим НОД (661 , 113) = 1 . Это значит, что 661 и 113 – это взаимно простые числа. Мы могли выяснить это до начала вычислений, если бы обратились к таблице простых чисел.
Ответ: НОД (661 , 113) = 1 .
Нахождение НОД с помощью разложения чисел на простые множители
Для того, чтобы найти наибольший общий делитель двух чисел методом разложения на множители, необходимо перемножить все простые множители, которые получаются при разложении этих двух чисел и являются для них общими.
Пример 4
Если мы разложим числа 220 и 600 на простые множители, то получим два произведения: 220 = 2 · 2 · 5 · 11 и 600 = 2 · 2 · 2 · 3 · 5 · 5 . Общими в этих двух произведениях будут множители 2 , 2 и 5 . Это значит, что НОД (220 , 600) = 2 · 2 · 5 = 20 .
Пример 5
Найдите наибольший общий делитель чисел 72 и 96 .
Решение
Найдем все простые множители чисел 72 и 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
Общими для двух чисел простые множители: 2 , 2 , 2 и 3 . Это значит, что НОД (72 , 96) = 2 · 2 · 2 · 3 = 24 .
Ответ: НОД (72 , 96) = 24 .
Правило нахождения наибольшего общего делителя двух чисел основано на свойствах наибольшего общего делителя, согласно которому НОД (m · a 1 , m · b 1) = m · НОД (a 1 , b 1) , где m – любое целое положительное число.
Нахождение НОД трех и большего количества чисел
Независимо от количества чисел, для которых нам нужно найти НОД, мы будем действовать по одному и тому же алгоритму, который заключается в последовательном нахождении НОД двух чисел. Основан этот алгоритм на применении следующей теоремы: НОД нескольких чисел a 1 , a 2 , … , a k равен числу d k , которое находится при последовательном вычислении НОД (a 1 , a 2) = d 2 , НОД (d 2 , a 3) = d 3 , НОД (d 3 , a 4) = d 4 , … , НОД (d k - 1 , a k) = d k .
Пример 6
Найдите наибольший общий делитель четырех чисел 78 , 294 , 570 и 36 .
Решение
Введем обозначения: a 1 = 78 , a 2 = 294 , a 3 = 570 , a 4 = 36 .
Начнем с того, что найдем НОД чисел 78 и 294: d 2 = НОД (78 , 294) = 6 .
Теперь приступим к нахождению d 3 = НОД (d 2 , a 3) = НОД (6 , 570) . Согласно алгоритму Евклида 570 = 6 · 95 . Это значит, что d 3 = НОД (6 , 570) = 6 .
Найдем d 4 = НОД (d 3 , a 4) = НОД (6 , 36) . 36 делится на 6 без остатка. Это позволяет нам получить d 4 = НОД (6 , 36) = 6 .
d 4 = 6 , то есть, НОД (78 , 294 , 570 , 36) = 6 .
Ответ:
А теперь давайте рассмотрим еще один способ вычисления НОД для тех и большего количества чисел. Мы можем найти НОД, перемножив все общие простые множители чисел.
Пример 7
Вычислите НОД чисел 78 , 294 , 570 и 36 .
Решение
Произведем разложение данных чисел на простые множители: 78 = 2 · 3 · 13 , 294 = 2 · 3 · 7 · 7 , 570 = 2 · 3 · 5 · 19 , 36 = 2 · 2 · 3 · 3 .
Для всех четырех чисел общими простыми множителями будут числа 2 и 3 .
Получается, что НОД (78 , 294 , 570 , 36) = 2 · 3 = 6 .
Ответ: НОД (78 , 294 , 570 , 36) = 6 .
Нахождение НОД отрицательных чисел
Если нам приходится иметь дело с отрицательными числами, то для нахождения наибольшего общего делителя мы можем воспользоваться модулями этих чисел. Мы можем так поступить, зная свойство чисел с противоположными знаками: числа n и - n имеют одинаковые делители.
Пример 8
Найдите НОД отрицательных целых чисел − 231 и − 140 .
Решение
Для выполнения вычислений возьмем модули чисел, данных в условии. Это будут числа 231 и 140 . Запишем это кратко: НОД (− 231 , − 140) = НОД (231 , 140) . Теперь применим алгоритм Евклида для нахождения простых множителей двух чисел: 231 = 140 · 1 + 91 ; 140 = 91 · 1 + 49 ; 91 = 49 · 1 + 42 ; 49 = 42 · 1 + 7 и 42 = 7 · 6 . Получаем, что НОД (231 , 140) = 7 .
А так как НОД (− 231 , − 140) = НОД (231 , 140) , то НОД чисел − 231 и − 140 равен 7 .
Ответ: НОД (− 231 , − 140) = 7 .
Пример 9
Определите НОД трех чисел − 585 , 81 и − 189 .
Решение
Заменим отрицательные числа в приведенном перечне на их абсолютные величины, получим НОД (− 585 , 81 , − 189) = НОД (585 , 81 , 189) . Затем разложим все данные числа на простые множители: 585 = 3 · 3 · 5 · 13 , 81 = 3 · 3 · 3 · 3 и 189 = 3 · 3 · 3 · 7 . Общими для трех чисел являются простые множители 3 и 3 . Получается, что НОД (585 , 81 , 189) = НОД (− 585 , 81 , − 189) = 9 .
Ответ: НОД (− 585 , 81 , − 189) = 9 .
Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
Найдем наибольший общий делитель НОД (36 ; 24)
Этапы решения
Способ №1
36
- составное число
24
- составное число
Разложим число 36
36:
2
= 18
18:
2
= 9
- делится на простое число 2
9:
3
=
3
- делится на простое число 3.
Разложим число 24 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
24:
2
= 12
- делится на простое число 2
12:
2
= 6
- делится на простое число 2
6:
2
=
3
Завершаем деление, так как 3 простое число
2) Выделим синим цветом и выпишем общие множители
36
=
2
⋅
2
⋅
3
⋅
3
24
=
2
⋅
2
⋅
2
⋅
3
Общие множители (36 ; 24) : 2, 2, 3
3) Теперь, чтобы найти НОД нужно перемножить общие множители
Ответ: НОД (36 ; 24) = 2 ∙ 2 ∙ 3 = 12
Способ №2
1) Найдем все возможные делители чисел (36 ; 24). Для этого поочередно разделим число 36 на делители от 1 до 36, число 24 на делители от 1 до 24. Если число делится без остатка, то делитель запишем в список делителей.
Для числа
36
36:
1
= 36;
36:
2
= 18;
36:
3
= 12;
36:
4
= 9;
36:
6
= 6;
36:
9
= 4;
36:
12
= 3;
36:
18
= 2;
36:
36
= 1;
Для числа
24
выпишем все случаи, когда оно делится без остатка:
24:
1
= 24;
24:
2
= 12;
24:
3
= 8;
24:
4
= 6;
24:
6
= 4;
24:
8
= 3;
24:
12
= 2;
24:
24
= 1;
2) Выпишем все общие делители чисел (36 ; 24) и выделим зеленым цветом самы большой, это и будет наибольший общий делитель НОД чисел (36 ; 24)
Общие делители чисел (36 ; 24): 1, 2, 3, 4, 6, 12
Ответ: НОД (36 ; 24) = 12
Найдем наименьшее общее кратное НОК (52 ; 49)
Этапы решения
Способ №1
1) Разложим числа на простые множители. Для этого проверим, является ли каждое из чисел простым (если число простое, то его нельзя разложить на простые множители, и оно само является своим разложением)
52
- составное число
49
- составное число
Разложим число 52 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
52:
2
= 26
- делится на простое число 2
26:
2
=
13
- делится на простое число 2.
Завершаем деление, так как 13 простое число
Разложим число 49 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
49:
7
=
7
- делится на простое число 7.
Завершаем деление, так как 7 простое число
2) Прежде всего запишем множители самого большого числа, а затем меньшего числа. Найдем недостающие множители, выделим синим цветом в разложении меньшего числа множители, которые не вошли в разложение большего числа.
52
= 2 ∙ 2 ∙ 13
49
=
7
∙
7
3) Теперь, чтобы найти НОК нужно перемножить множители большего числа с недостающими множителями, которые выделены синим цветом
НОК (52 ; 49) = 2 ∙ 2 ∙ 13 ∙ 7 ∙ 7 = 2548
Способ №2
1) Найдем все возможные кратные чисел (52 ; 49). Для этого поочередно умножим число 52 на числа от 1 до 49, число 49 на числа от 1 до 52.
Выделим все кратные числа 52 зеленым цветом:
52 ∙ 1 =
52
;
52 ∙ 2 =
104
;
52 ∙ 3 =
156
;
52 ∙ 4 =
208
;
52 ∙ 5 =
260
;
52 ∙ 6 =
312
;
52 ∙ 7 =
364
;
52 ∙ 8 =
416
;
52 ∙ 9 =
468
;
52 ∙ 10 =
520
;
52 ∙ 11 =
572
;
52 ∙ 12 =
624
;
52 ∙ 13 =
676
;
52 ∙ 14 =
728
;
52 ∙ 15 =
780
;
52 ∙ 16 =
832
;
52 ∙ 17 =
884
;
52 ∙ 18 =
936
;
52 ∙ 19 =
988
;
52 ∙ 20 =
1040
;
52 ∙ 21 =
1092
;
52 ∙ 22 =
1144
;
52 ∙ 23 =
1196
;
52 ∙ 24 =
1248
;
52 ∙ 25 =
1300
;
52 ∙ 26 =
1352
;
52 ∙ 27 =
1404
;
52 ∙ 28 =
1456
;
52 ∙ 29 =
1508
;
52 ∙ 30 =
1560
;
52 ∙ 31 =
1612
;
52 ∙ 32 =
1664
;
52 ∙ 33 =
1716
;
52 ∙ 34 =
1768
;
52 ∙ 35 =
1820
;
52 ∙ 36 =
1872
;
52 ∙ 37 =
1924
;
52 ∙ 38 =
1976
;
52 ∙ 39 =
2028
;
52 ∙ 40 =
2080
;
52 ∙ 41 =
2132
;
52 ∙ 42 =
2184
;
52 ∙ 43 =
2236
;
52 ∙ 44 =
2288
;
52 ∙ 45 =
2340
;
52 ∙ 46 =
2392
;
52 ∙ 47 =
2444
;
52 ∙ 48 =
2496
;
52 ∙ 49 =
2548
;
Выделим все кратные числа 49 зеленым цветом:
49 ∙ 1 =
49
;
49 ∙ 2 =
98
;
49 ∙ 3 =
147
;
49 ∙ 4 =
196
;
49 ∙ 5 =
245
;
49 ∙ 6 =
294
;
49 ∙ 7 =
343
;
49 ∙ 8 =
392
;
49 ∙ 9 =
441
;
49 ∙ 10 =
490
;
49 ∙ 11 =
539
;
49 ∙ 12 =
588
;
49 ∙ 13 =
637
;
49 ∙ 14 =
686
;
49 ∙ 15 =
735
;
49 ∙ 16 =
784
;
49 ∙ 17 =
833
;
49 ∙ 18 =
882
;
49 ∙ 19 =
931
;
49 ∙ 20 =
980
;
49 ∙ 21 =
1029
;
49 ∙ 22 =
1078
;
49 ∙ 23 =
1127
;
49 ∙ 24 =
1176
;
49 ∙ 25 =
1225
;
49 ∙ 26 =
1274
;
49 ∙ 27 =
1323
;
49 ∙ 28 =
1372
;
49 ∙ 29 =
1421
;
49 ∙ 30 =
1470
;
49 ∙ 31 =
1519
;
49 ∙ 32 =
1568
;
49 ∙ 33 =
1617
;
49 ∙ 34 =
1666
;
49 ∙ 35 =
1715
;
49 ∙ 36 =
1764
;
49 ∙ 37 =
1813
;
49 ∙ 38 =
1862
;
49 ∙ 39 =
1911
;
49 ∙ 40 =
1960
;
49 ∙ 41 =
2009
;
49 ∙ 42 =
2058
;
49 ∙ 43 =
2107
;
49 ∙ 44 =
2156
;
49 ∙ 45 =
2205
;
49 ∙ 46 =
2254
;
49 ∙ 47 =
2303
;
49 ∙ 48 =
2352
;
49 ∙ 49 =
2401
;
49 ∙ 50 =
2450
;
49 ∙ 51 =
2499
;
49 ∙ 52 =
2548
;
2) Выпишем все общие кратные чисел (52 ; 49) и выделим зеленым цветом самое маленькое, это и будет наименьшим общим кратным чисел (52 ; 49).
Общие кратные чисел (52 ; 49): 2548
Ответ: НОК (52 ; 49) = 2548