Как найти нок чисел алгоритм евклида

Как найти нок чисел алгоритм евклида

Автор статьи

Эксперт по предмету «Математика»

Задать вопрос автору статьи

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

Определение 2

Если натуральное число a делится на натуральное число $b$, то $b$ называют делителем числа $a$, а число $a$ называют кратным числа $b$.

Пусть $a$ и $b$-натуральные числа. Число $c$ называют общим делителем и для $a$ и для $b$.

Множество общих делителей чисел $a$ и $b$ конечно, так как ни один из этих делителей не может быть больше, чем $a$. Значит ,среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел $a$ и $b$ и для его обозначения используют записи :

$НОД (a;b) или D (a;b)$

Чтобы найти наибольший общий делитель двух, чисел необходимо:

  1. разложить числа на простые множители
  2. Выбрать числа, которые входят в разложение этих чисел
  3. Найти произведение чисел , найденных на шаге 2. Полученное число и будет искомым наибольшим общим делителем.

Пример 1

Найти НОД чисел $121$ и $132.$

Будем находить согласно представленному алгоритму. Для этого

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

    $242=2cdot 11cdot 11$

    $132=2cdot 2cdot 3cdot 11$

  2. Выбрать числа, которые входят в разложение этих чисел

    $242=2cdot 11cdot 11$

    $132=2cdot 2cdot 3cdot 11$

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

    $НОД=2cdot 11=22$

Пример 2

Найти НОД одночленов $63$ и $81$.

Будем находить согласно представленному алгоритму. Для этого:

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

    $63=3cdot 3cdot 7$

    $81=3cdot 3cdot 3cdot 3$

  2. Выбираем числа, которые входят в разложение этих чисел

    $63=3cdot 3cdot 7$

    $81=3cdot 3cdot 3cdot 3$

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

    $НОД=3cdot 3=9$

«НОД и НОК двух чисел, алгоритм Евклида» 👇

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

Пример 3

Найти НОД чисел $48$ и $60$.

Решение:

Найдем множество делителей числа $48$: $left{{rm 1,2,3.4.6,8,12,16,24,48}right}$

Теперь найдем множество делителей числа $60$:$ left{{rm 1,2,3,4,5,6,10,12,15,20,30,60}right}$

Найдем пересечение этих множеств: $left{{rm 1,2,3,4,6,12}right}$- данное множество будет определять множество общих делителей чисел $48$ и $60$. Наибольший элемент в данном множестве будет число $12$. Значит наибольший общий делитель чисел $48$ и $60$ будет $12$.

$D(48;60)=12$

Определение НОК

Определение 3

Общим кратным натуральных чисел $a$ и $b$ называется натуральное число, которое кратно и $a$ и $b$.

Общими кратными чисел называются числа которые делятся на исходные без остатка.Например для чисел $25$ и $50$ общими кратными будут числа $50,100,150,200$ и т.д

Наименьшее из общих кратных будет называться наименьшим общим кратным и обозначается НОК$(a;b)$ или K$(a;b).$

Чтобы найти НОК двух чисел, необходимо:

  1. Разложить числа на простые множители
  2. Выписать множители, входящие в состав первого числа и добавить к ним множители, которые входят в состав второго и не ходят в состав первого
  3. Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наименьшим общим кратным

Пример 4

Найти НОК чисел $99$ и $77$.

Будем находить согласно представленному алгоритму. Для этого

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

    $99=3cdot 3cdot 11$

    $77=7cdot 11$

  2. Выписать множители, входящие в состав первого

    $3,3,11$

    добавить к ним множители, которые входят в состав второго и не ходят в состав первого

    $7$

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

    $НОК=3cdot 3cdot 11cdot 7=693$

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

    Утверждения, на которых основан алгоритм Евклида:

  4. Если $a$ и $b$ –натуральные числа, причем $avdots b$, то $D(a;b)=b$

  5. Если $a$ и $b$ –натуральные числа, такие что $b

Пользуясь $D(a;b)= D(a-b;b)$, можно последовательно уменьшать рассматриваемые числа до тех пор, пока не дойдем до такой пары чисел, что одно из них делится на другое. Тогда меньшее из этих чисел и будет искомым наибольшим общим делителем для чисел $a$ и $b$.

Свойства НОД и НОК

  1. Любое общее кратное чисел $a$ и $b$ делится на K$(a;b)$
  2. Если $avdots b$ , то К$(a;b)=a$

  3. Если К$(a;b)=k$ и $m$-натуральное число, то К$(am;bm)=km$

    Если $d$-общий делитель для $a$ и $b$,то К($frac{a}{d};frac{b}{d}$)=$ frac{k}{d}$

  4. Если $avdots c$ и $bvdots c$ ,то $frac{ab}{c}$ – общее кратное чисел $a$ и $b$

  5. Для любых натуральных чисел $a$ и $b$ выполняется равенство

    $D(a;b)cdot К(a;b)=ab$

  6. Любой общийй делитель чисел $a$ и $b$ является делителем числа $D(a;b)$

Находи статьи и создавай свой список литературы по ГОСТу

Поиск по теме

Источник

Что такое нок в математике? Продолжим разговор о наименьшем общем кратном, который мы начали в разделе « НОК – наименьшее общее кратное, определение, примеры». В этой теме мы узнаем, как найти наименьшее общее кратное, какие есть для этого способы для трех чисел и более, разберем вопрос о том, как находить НОК отрицательного числа. Также разберемся, что такое нок и нод, как найти нок и нод. 

Вычисление наименьшего общего кратного (НОК) через НОД

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

Определение 1

Поиск наименьшего общего кратного через наибольший общий делитель можно по формуле НОК(a, b)=a·b:НОД(a, b).

Пример 1

Необходимо найти НОК чисел 126 и 70.

Решение

Начнем решать. Примем a=126, b=70. Подставим значения в формулу вычисления наименьшего общего кратного через наибольший общий делитель НОК(a, b)=a·b:НОД(a, b).

Найдем НОД чисел 70 и 126. Для этого нам понадобится алгоритм Евклида: 126=70·1+56, 70=56·1+14, 56=14·4, следовательно, NOD(126, 70)=14.

Вычислим НОК: НОК(126, 70)=126·70:НОД(126, 70)=126·70:14=630.

Ответ: NOC(126, 70)=630.

Пример 2

Найдите нок чисел 68 и 34.

Решение

Как находить нод? НОД в данном случае нейти несложно, так как 68 делится на 34. Вычислим самое маленькое общее кратное по формуле: НОК(68, 34)=68·34:НОД(68, 34)=68·34:34=68.

Ответ: НОК(68, 34)=68.

В этом примере мы использовали правило нахождения наименьшего общего кратного для целых положительных чисел a и b: если первое число делится на второе, что НОК этих чисел будет равно первому числу.

Нахождение НОК с помощью разложения чисел на простые множители

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

Определение 2

Для нахождения наименьшего общего кратного нам понадобится выполнить ряд несложных действий:

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

Этот способ нахождения наименьшего общего кратного основан на равенстве НОК(a, b)=a·b:НОД(a, b). Если посмотреть на формулу, то станет понятно: произведение чисел a и b равно произведению всех множителей, которые участвуют в разложении этих двух чисел. При этом НОД двух чисел равен произведению всех простых множителей, которые одновременно присутствуют в разложениях на множители данных двух чисел.

Пример 3

У нас есть два числа 75 и 210. Мы можем разложить их на множители следующим образом: 75=3·5·5 и 210=2·3·5·7. Если составить произведение всех множителей двух исходных чисел, то получится: 2·3·3·5·5·5·7.

Если исключить общие для обоих чисел множители 3 и 5, мы получим произведение следующего вида: 2·3·5·5·7=1050. Это произведение и будет нашим НОК для чисел 75 и 210.

Пример 4

Найдите НОК чисел 441 и 700, разложив оба числа на простые множители.

Решение

Найдем все простые множители чисел, данных в условии:

44114749713377

700350175357122557

Получаем две цепочки чисел: 441=3·3·7·7 и 700=2·2·5·5·7.

Произведение всех множителей, которые участвовали в разложении данных чисел, будет иметь вид: 2·2·3·3·5·5·7·7·7. Найдем общие множители. Это число 7. Исключим его из общего произведения: 2·2·3·3·5·5·7·7. Получается, что НОК(441, 700)=2·2·3·3·5·5·7·7=44 100.

Ответ: НОК(441, 700)= 44 100.

Дадим еще одну формулировку метода нахождения НОК путем разложения чисел на простые множители.

Определение 3

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

  • разложим оба числа на простые множители:
  • добавим к произведению простых множителей первого числа недостающие множители второго числа;
  • получим произведение, которое и будет искомым НОК двух чисел.
Пример 5

Вернемся к числам 75 и 210, для которых мы уже пробовали искать НОК в одном из прошлых примеров. Разложим их на простые множители: 75=3·5·5 и 210=2·3·5·7. К произведению множителей 3, 5 и 5 числа 75 добавим недостающие множители 2 и 7 числа 210. Получаем: 2·3·5·5·7. Это и есть НОК чисел 75 и 210.

Пример 6

Необходимо вычислить НОК чисел 84 и 648.

Решение

Разложим числа из условия на простые множители: 84=2·2·3·7 и 648=2·2·2·3·3·3·3. Добавим к произведению множителей 2, 2, 3 и 7 числа 84 недостающие множители 2, 3, 3 и
3 числа 648. Получаем произведение 2·2·2·3·3·3·3·7=4536. Это и есть наименьшее общее кратное чисел 84 и 648​​​​​​ ​.

Ответ: НОК(84, 648)=4 536.

Нахождение НОК трех и большего количества чисел

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

Теорема 1

Предположим, что у нас есть целые числа a1, a2, …, ak. НОК mk этих чисел находится при последовательном вычислении m2=НОК(a1, a2), m3=НОК(m2, a3), …, mk=НОК(mk−1, ak).

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

Пример 7

Необходимо вычислить наименьшее общее кратное четырех чисел 140, 9, 54 и 250.

Решение задания

Введем обозначения: a1=140, a2=9, a3=54, a4=250.

Начнем с того, что вычислим m2=НОК(a1, a2)=НОК(140, 9). Применим алгоритм Евклида для вычисления НОД чисел 140 и 9: 140=9·15+5, 9=5·1+4, 5=4·1+1, 4=1·4. Получаем: НОД(140, 9)=1, НОК(140, 9)=140·9:НОД(140, 9)=140·9:1=1 260. Следовательно, m2=1 260.

Теперь вычислим по тому е алгоритму m3=НОК(m2, a3)=НОК(1 260, 54). В ходе вычислений получаем m3=3 780.

Нам осталось вычислить m4=НОК(m3, a4)=НОК(3 780, 250). Действуем по тому же алгоритму. Получаем m4=94 500.

НОК четырех чисел из условия примера равно 94500.

Ответ: НОК(140, 9, 54, 250)=94 500.

Как видите, вычисления получаются несложными, но достаточно трудоемкими. Чтобы сэкономить время, можно пойти другим путем.

Определение 4

Предлагаем вам следующий алгоритм действий: 

  • раскладываем все числа на простые множители;
  • к произведению множителей первого числа добавляем недостающие множители из произведения второго числа;
  • к полученному на предыдущем этапе произведению добавляем недостающие множители третьего числа и т.д.;
  • полученное произведение будет наименьшим общим кратным всех чисел из условия.
Пример 8

Необходимо найти НОК пяти чисел 84, 6, 48, 7, 143.

Решение

Разложим все пять чисел на простые множители: 84=2·2·3·7, 6=2·3, 48=2·2·2·2·3, 7, 143=11·13. Простые числа, которым является число 7, на простые множители не раскладываются. Такие числа совпадают со своим разложением на простые множители.

Теперь возьмем произведение простых множителей 2, 2, 3 и 7 числа 84 и добавим к ним недостающие множители второго числа. Мы разложили число 6 на 2 и 3. Эти множители уже есть в произведении первого числа. Следовательно, их опускаем.

Продолжаем добавлять недостающие множители. Переходим к числу 48, из произведения простых множителей которого берем 2 и 2. Затем добавляем простой множитель 7 от четвертого числа и множители 11 и 13 пятого. Получаем: 2·2·2·2·3·7·11·13=48 048. Это и есть наименьшее общее кратное пяти исходных чисел.

Ответ: НОК(84, 6, 48, 7, 143)=48 048.

Нахождение наименьшего общего кратного отрицательных чисел

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

Пример 9

НОК(54, −34)=НОК(54, 34), а НОК(−622, −46, −54, −888)=НОК(622, 46, 54, 888).

Такие действия допустимы в связи с тем, что если принять, что a и −a – противоположные числа,
то  множество кратных числа a совпадает со множеством кратных числа −a.

Пример 10

Необходимо вычислить НОК отрицательных чисел −145 и −45.

Решение

Произведем замену чисел −145 и −45 на противоположные им числа 145 и 45. Теперь по алгоритму вычислим НОК(145, 45)=145·45:НОД(145, 45)=145·45:5=1 305, предварительно определив НОД по алгоритму Евклида.

Получим, что НОК чисел −145 и −45 равно 1 305.

Ответ: НОК(−145, −45)=1 305.

Ирина Мальцевская

Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта

Источник

Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления.

Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3. А далее находим НОК (наименьшее) общее кратное). Которое будет равно 30.

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

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

Легко находим НОК или НОД с помощью алгоритма Евклида

Мы с вами уже находили НОД для 6 и 15. И у нас также получилось 3.

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

Пусть будут числа 195 и 1450. Очевидно, что они точно деляться на 5, но я предлагаю проверить.

Легко находим НОК или НОД с помощью алгоритма Евклида

И действительно 195 = 3*5*13, а 1450 = 2*5*5*29.

А теперь рассмотрим как найти НОК (наименьшее общее кратное). Рассмотрим сперва на простом примере. Числа 15 и 6.

Есть такая замечательная формула НОК = (A*B) / НОД.

Теперь проверим это выражение. НОК = (15*6)/3=30.

Оказывается, что всё достаточно просто. Если рассмотреть числа 195 и 1450, то для них НОК будет 195*1450/5=56550 или 2*3*5*5*13*29.

То есть без калькулятора можно свободно найти НОД и НОК. Естественно что для программиста эта задача становится очень простой.

Для начала разберем алгоритм через блок-схему.

Легко находим НОК или НОД с помощью алгоритма Евклида

Подробнее можно увидеть на видео:

У меня всё, благодарю за внимание.

———————————————————————-

Делюсь другими материалами:

Сериал Дистанционка от коллег в А1: Дистанционка. Серия 1. Дистанционка. Серия 2. Дистанционка. Серия 3.

Материалы по Scratch.

Источник

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

Как несложно догадаться, наибольший общий делитель (англ. greatest
common divisor) двух целых чисел – наибольшее число, на которое делится
каждое из них. Например:

[gcd(15, 20) = 5]

[gcd(12, 30) = 6]

Сразу заметим важное свойство:

[gcd(a, b) = gcd(b, a)]

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

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

Алгоритм Евклида – один из первых алгоритмов в истории, использовался
ещё в Древней Греции, и дошёл до наших дней. В изначальном виде он назывался
“взаимным вычитанием”, так как заключался в поочерёдном вычитании меньшего
числа из большего, пока одно из них не станет равным 0. Сегодня чаще всего
вместо вычитания используется взятие остатка от деления, но суть алгоритма
сохранилась.

Алгоритм заключается в построении ряда чисел следующего вида ((a > b)):

[a, b, r_1, r_2, ldots, r_n]

Где каждое последующее число является остатком от деления предпредыдущего
на предыдущее:

[r_1 = a bmod b \
r_2 = b bmod r_1 \
ldots \
r_n = r_{n – 2} bmod r_{n – 1}]

Ряд заканчивается, когда остаток от деления предпоследнего числа на
последнее становится равным 0:

[r_{n – 1} bmod r_n = 0]

В таком случае утверждается, что:

[gcd(a, b) = r_n]

Для доказательства этого утверждения сначала докажем следующее:
наборы общих делителей пары ((a, b)) и пары ((b, r_1)) полностью совпадают.
Рассмотрим произвольный (не обязательно наибольший) общий делитель (a) и (b):

(t) – общий делитель (a) и (b).

(r_1 = a bmod b), или (a = bq + r_1).

Докажем, что (t) также является общим делителем (b) и (r_1).

(b) делится на (t) по определению.

(r_1 = a – bq = t * ({a over t} – {b over t} * q)), где ({a over t}) и ({b over t}) целые по определению.

Значит, (r_1) также делится на (t), что и требовалось доказать.

Из того, что все общие делители пар ((a, b)) и ((b, r_1)) совпадают,
в частности следует, что (gcd(a, b) = gcd(b, r_1)).

Далее по индукции можно доказать следующее:

[gcd(a, b) = gcd(b, r_1) = gcd(r_1, r_2) = ldots = gcd(r_{n – 1}, r_n) = gcd(r_n, 0)]

(Нуль в последнем выражении появился из условия (r_{n – 1} bmod r_n = 0)).

Нуль делится на все числа, отличные от нуля, поэтому справедливо следующее
свойство:

[gcd(x, 0) = x, для любого x in mathbb{N}.]

Следовательно,

[gcd(a, b) = r_n,]

что и требовалось доказать.

Варианты реализации алгоритма Евклида на C++

Существует несколько вариантов реализации алгоритма Евклида, как итеративных
так и рекурсивных. Классическая итеративная реализация (работающая быстрее всех
рекурсивных) выглядит так:

1
2
3
4
5
6
7
8
9
10
11
12





int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }

    while (b) {
        a %= b;
        swap(a, b);
    }

    return a;
}











Рекурсивно это же можно реализовать так:


1
2
3
4
5
6
7
8
9
10
11





int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }

    if (b) {
        return gcd(b, a % b);
    } else {
        return a;
    }
}











Преимущество рекурсивной реализации заключается в возможности записать её в

очень кратком виде (предполагающим, что (a > b)):


1
2
3





int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}











На практике разница во времени работы итеративного и рекурсивного вариантов

не столь значительна, так что вы можете использовать любой из них.


Время работы алгоритма Евклида


Согласно некоторым исследованиям, время работы алгоритма Евклида тесно

связано с числами Фибоначчи. Это выражается, в частности, в том, что два

последовательных числа Фибоначчи – наихудшие входные данные для алгоритма

Евклида. При (a = F_n, b = F_{n – 1}), алгоритм Евклида совершит ровно

(n – 2) итерации. Отсюда можно выразить асимптотическую сложность алгоритма:

последовательность Фибоначчи возрастает с экспоненциальной скоростью, поэтому

алгоритм Евклида работает за (O(log min(a, b))).


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


С понятием НОД связано также понятия наименьшего общего кратного (англ.

least common multiple). Наименьшее общее кратное двух натуральных чисел –

наименьшее натуральное число, которое делится на каждое из них. Оно обозначается

следующим образом:


[lcm(a, b)]


и связано с НОД формулой:


[lcm(a, b) = {a * b over gcd(a, b)}]


Реализация на C++:


1
2
3
4
5





int lcm(int a, int b) {
    return a / gcd(a, b) * b;   //используя форму a * b / gcd(a, b),
                                //можно получить переполнение на этапе a * b,
                                //поэтому следует выполнять деление до умножения
}











Взаимнопростые числа


Числа (a) и (b) называются взаимнопростыми тогда и только тогда, когда они

не имеют общих делителей отличных от (1). То есть в их отношении должно

выполняться условие (gcd(a, b) = 1).


НОД и НОК для произвольного количества чисел


Обе функции легко обобщаются для произвольного числа аргументов

последовательным применением:


[gcd(a, b, c, d) = gcd(gcd(gcd(a, b), c), d)]


[lcm(a, b, c, d) = lcm(lcm(lcm(a, b), c), d)]
Источник

Нахождение НОК и НОД двух натуральных чисел

Содержание:

  • Что такое НОК и НОД двух натуральных чисел
  • Особенности вычисления, алгоритм Евклида
  • Правило нахождения наибольшего общего делителя (НОД)
  • Правило нахождения наименьшего общего кратного (НОК)

Что такое НОК и НОД двух натуральных чисел

Натуральными числами называют числа, которые используются при счете – 1, 2, 3, 16, 25, 101, 2560 и далее до бесконечности. Ноль, отрицательные и дробные или нецелые числа не относятся к натуральным.

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

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

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

Свойства НОК и НОД для натуральных чисел a и b

  • (НОД (a, b) = НОД (b, a);)
  • (НОК (a, b) = НОК (b, a);)
  • (НОК;(a,b)=frac{a;times;b}{НОД;(a,b)}.)

Особенности вычисления, алгоритм Евклида

Рассмотрим два способа определения НОД и НОК с помощью алгоритма Евклида:

  • Способ деления.

При делении целых чисел с остатком, где a – делимое, b – делитель (b не равно 0) находят целые числа q и r согласно равенству (a=btimes) q+r, в котором q – неполное частное, r – остаток при делении (не отрицательное, по модулю меньше делителя).

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

Пример №1

Вычислим НОД для чисел 12 и 20. Делим 20 на 12 и получаем 1 и 8 в остатке. Запишем иначе:

(20=12times1+8), так как остаток не равняется нулю, продолжаем деление. Делим 12 на 8 и получаем 1 и 4 в остатке. Записываем: (12=8times1+4) и по аналогии делим 8 на 4 и получаем 2 и 0 в остатке. НОД равен остатку, предшествующему нулю.

НОД (12;20) = 4

НОК получаем согласно свойству (НОК (a, b) = НОК;(a,b)=frac{a;times;b}{НОД;(a,b)}.) Подставляем числовые значения:

НОК (12; 20) = (12times20div4=60)

НОК (12;20) = 60

  • Способ вычитания.

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

Пример №2

Вычислим НОД для тех же чисел, 12 и 20.

20 – 12 = 8 (разность не равна нулю, продолжаем)

12 – 8 = 4

8 – 4 = 4

4 – 4 = 0

НОД (12;20) = 4

НОК находим также, как и при методе деления.

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

Для нахождения наибольшего общего делителя воспользуемся пошаговым алгоритмом:

  1. Разложить числа на простые множители.
  2. Найти общий множитель одного и другого числа.
  3. Перемножить общие множители, если их несколько, и их произведение будет НОД.

Пример №3

Возьмем натуральные числа 24 и 36.

(24=2times2times2times3)

(36=2times2times3times3)

Правильно записать следующим образом:

(НОД (24;36)=2times3=6)

Примечание

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

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

Для нахождения наименьшего общего кратного воспользуемся подробным алгоритмом:

  1. Наибольшее из чисел, а затем остальные разложить на простые множители.
  2. Выделить те множители, которые отсутствуют у наибольшего.
  3. Перемножить множители п. 2 и множители наибольшего числа, получить НОК.

Пример №4

Возьмем натуральные числа 9 и 12.

(12=2times2times3)

(9=3times3) (видим, что у числа 12 отсутствует одна тройка)

Правильно записать следующим образом:

(НОК (9;12)=2times2times3times3=36)

Насколько полезной была для вас статья?

Рейтинг: 3.00 (Голосов: 4)

Выделите текст и нажмите одновременно клавиши «Ctrl» и «Enter»

Текст с ошибкой:

Расскажите, что не так

Поиск по содержимому

Источник

Добавить комментарий