Как быстро найти нод двух чисел

Как найти НОД

  • Нахождение путём разложения на множители
  • Алгоритм Евклида

Рассмотрим два способа нахождения наибольшего общего делителя.

Нахождение путём разложения на множители

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

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

Пример 1. Найти НОД (84, 90).

Решение: Раскладываем числа  84  и  90  на простые множители:

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

Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой:

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.

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

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

Пример 2. Найдём наибольший общий делитель чисел  140  и  96:

1) 140 : 96 = 1 (остаток 44)

2) 96 : 44 = 2 (остаток 8)

3) 44 : 8 = 5 (остаток 4)

4) 8 : 4 = 2

Последний делитель равен  4  — это значит:

НОД (140, 96) = 4.

Последовательное деление так же можно записывать столбиком:

как найти нод чисел

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

  1. Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
  2. Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
  3. Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.

Пример 3. Найдём наибольший общий делитель чисел  140,  96  и  48.  НОД чисел  140  и  96  мы уже нашли в предыдущем примере (это число  4).  Осталось найти наибольший общий делитель числа  4  и третьего данного числа —  48:

48 : 4 = 12

48  делится на  4  без остатка. Таким образом:

НОД (140, 96, 48) = 4.

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

Содержание:

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

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

Натуральными числами называют числа, которые используются при счете – 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»

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

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

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

Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 12 и 8, наибольшим общим делителем будет 4.

Как найти НОД?

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

  1. разложить оба числа на простые множители (подробнее о разложении чисел на простые множители смотрите тут);
  2. выбрать одинаковые множители, входящие в оба разложения;
  3. найти их произведение.

Примеры нахождения наибольшего общего делителя

Рассмотрим приведенный алгоритм на конкретных примерах:

Пример 1: найти НОД 12 и 8

1. Раскладываем 12 и 8 на простые множители:

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

3. Перемножаем эти множители и получаем: 2 · 2 = 4

Ответ: НОД (8; 12) = 2 · 2 = 4.

Пример 2: найти НОД 75 и 150

Этот пример, как и предыдущий с легкостью можно высчитать в уме и вывести ответ 75, но для лучшего понимания работы алгоритма, проделаем все шаги:

1. Раскладываем 75 и 150 на простые множители:

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 3, 5 и 5

3. Перемножаем эти множители и получаем: 3 · 5 · 5 = 75

Ответ: НОД (75; 150) = 3 · 5 · 5 = 75.

Частный случай или взаимно простые числа

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

Пример 3: найти НОД 9 и 5

1. Раскладываем 5 и 9 на простые множители:

Видим, что одинаковых множителей нет, а значит, что это частный случай (взаимно простые числа). Общий делитель — единица.

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

Оглавление:

  • Признаки делимости
  • Разложение на простые элементы
  • Нахождение НОД
  • Определение НОК

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

Как найти наибольший общий делитель для двух чисел

Общие сведения

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

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

  1. Определения величин.
  2. Признаки делимости чисел.
  3. Разложение на простые элементы или множители.
  4. Алгоритмы или методики нахождения.

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

Первый элемент — делимое, т. е. оно делится на определенный элемент (делитель). Результатом является частное. Математики называют последнее частным двух или более значений. Далее нужно разобрать признаки делимости.

Признаки делимости

В математике существуют 2 понятия: цифры и числа. Главное отличие — при комбинации цифр получаются числа. Кроме того, каждое значение состоит из разрядов (единиц, десятков, сотен, тысяч). Последние читаются слева направо, т. е. 657 состоит из единиц (7), десятков (5) и сотен (6). Если объединить их, получится искомая величина. Операция имеет такой вид: 7+50+600=657.

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

Признаки делимости

  1. R (любое действительное число).
  2. Последняя цифра — четная, т. е. 24/2 — делится, т. к. 4 — четное.
  3. Сумма цифр, составляющих число, возможно разделить на 3. Пример: 36/3={3+6=9/3=9}=12.
  4. Последние 2 цифры можно разделить на 4, т. е. 844/4={44/4=11}=211.
  5. Последний разряд эквивалентен одному из двух значений (0 или 5), 810/5={0}=162.
  6. Для числа 6 одновременно выполняются второй и третий пункт. Пример: 96/6={6-четное} и {9+6=15/3=15}=16.
  7. 7: расчет по формуле [a*b*c*d+e]/7, где e — разряд единиц, а все остальные (слева направо) — десятки, сотни, тысячи и десятки тысяч. Правило справедливо и для величин с разным количеством разрядов. Пример: 861/7={(8*6+1)/7=49/7=7}=123.
  8. Деление на 8 осуществляется по второму и четвертому признакам одновременно, т. е. 184/8={4 — четное} и {84/4=21}=23.
  9. Сумму разрядов можно разделить на 9. Пример: 108/9={1+0+8=9/9=1}=12.
  10. Последняя цифра эквивалентна 0, т. е. 140/10={0}=14.
  11. 2 разряда равны между собой (11, 22, 33 и т. д. ) или величина, образованная разрядами сотен и десятков без единиц, делится на 11 (121={(12−1)/11=1}).

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

Разложение на простые элементы

Простые множители — числа, которые делятся только на единицу или на эквивалентную величину, т. е. 7/1 и 7/7. Разложение величины на простые элементы — найти совокупность чисел, произведение которых и будет составлять искомое значение. Например, 30=3*5*2. Для выполнения этой операции математики разработали специальный алгоритм:

  1. Написать значение.
  2. Определить по признакам делимости первый множитель.
  3. Выполнить операцию деления.
  4. Подобрать второй множитель для величины, полученной в 3 пункте.
  5. Реализовать пункты со 2 по 4 включительно.

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

Ученики решают

  1. 176.
  2. 2: 176/2=88.
  3. 11: 88/11=8.
  4. 2: 8/2=4.
  5. 2: 4/2=2.
  6. 2: 2/2=1.

Следовательно, 176=2*11*2*2*2. Однако результат можно записать в более упорядоченной форме: 176=11*2*2*2*2*2. Далее следует перейти к алгоритмам, посредством которых можно вычислить НОК и НОД.

Нахождение НОД

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

  1. Раскладываются первое и второе значения на простые множители.
  2. Выбираются общие множители и перемножаются между собой.

Для реализации методики на практике нужно разобрать нахождение НОД 86 и 92. Она имеет такой вид:

  1. 92: 92/2=46/2=23, т. е. 92=23*2*2.
  2. 86: 86/2=43*2.
  3. НОД: 2.

Наиболее простой является методика Евклида для нахождения НОД. Она позволяет быстро найти искомое значение и имеет такой вид:

Нахождение НОД

  1. Разделить большее значение на меньшее (записать отдельно целую часть и остаток).
  2. Если есть остаток, искомое большое число нужно на него разделить.
  3. Выполнять пункты алгоритма, пока остаток не будет равным 0. Результат — это и есть НОД.

Чтобы понять смысл, нужно применить ее к числам 92 и 86. Это выглядит следующим образом:

  1. 92/86=1{6}.
  2. 86/6=14{2}.
  3. 14/2=7{0}.
  4. НОД=2, т. к. в третьем пункте нет остатка от деления.

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

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

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

  1. Разложить величины на множители.
  2. Взять наименьшее и дополнить его недостающими элементами.
  3. Вычислить искомое значение НОК.

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

  1. 18=3*3*2.
  2. 12=2*2*3.
  3. НОК=12*3=36.

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

Примеры решения

Одной из сложных задач является следующая: найти наибольший общий делитель чисел 32, 66 и 84. Для решения можно воспользоваться одним из способов. Оптимальным из них является разложение на множители:

  1. 32=2*2*2*2*2.
  2. 66=11*3*2.
  3. 84=2*3*2*2*2*2.
  4. НОД=2.

По методике Евклида решать не рекомендуется, т. к. это усложнит вычисления. Основной принцип физико-математических дисциплин — оптимизация расчетов, т. е. нужно искать способ с наименьшим количеством преобразований и расчетов.

В следующей задаче требуется осуществить поиск НОД для 66, 121, 77 и 110. В этом случае также рекомендуется разложить на простые множители все 4 числа. Поиск решения выполняется по такой методике:

Решение примеров

  1. 66=11*3*2.
  2. 121=11*11.
  3. 77=11*7.
  4. 110=11*5*2.
  5. НОД=11.

Если рассмотреть 2 этих примера, можно сделать вывод, что считать НОД довольно просто. Далее нужно найти НОК для 22 и 32. Это осуществляется по такой методике:

  1. 22=11*2.
  2. 32=8*4=2*2*2*2*2.
  3. НОК=11*2*2*2*2*2=22*16=352.

Еще одним типом задачи является одновременное нахождение НОД и НОК для чисел 45, 85, 94 и 96. Решение имеет следующий вид:

  1. 45=5*3*3.
  2. 85=17*5.
  3. 94=2*47.
  4. 96=2*2*3*2*2*2.
  5. НОД=1 (нет общих множителей, кроме единицы).
  6. НОК=5*3*3*17*2*47*2*2*2*2*2=1150560.

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

  1. 90=9*10.
  2. 81=9*9.
  3. НОД=9.

Задача решается методом подбора, поскольку по условию ближайшая целая величина эквивалентна 81.

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

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


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

4.3

Средняя оценка: 4.3

Всего получено оценок: 224.

4.3

Средняя оценка: 4.3

Всего получено оценок: 224.

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

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

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

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

Как найти НОД?

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

Специальной формулы для этого не придумали, зато есть алгоритм вычисления.

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

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

Теперь проведем ту же процедуру на практике.

  • 540 : 2=270
  • 270:2=135
  • 135 : 3 =45
  • 45 : 3=15
  • 15 : 5 = 3

Запишем результат в виде равенства 540=2*2*3*3*3*5. Для того, чтобы записать результат, нужно последнее получившееся число умножить на все делители.

Аналогично поступим с числом 252:

  • 252 : 2=126
  • 126: 2=63
  • 63 : 3=21
  • 21 : 3 = 7

Запишем результат: 252=2*2*3*3*7.

В каждом разложении есть одинаковые числа. Найдем их, это два числа 2 и два числа 3. Отличаются только 7 и 3*5.

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

НОД=2*2*3*3=36

Как можно это использовать?

Задача: сократить дробь $$252over540$$.

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

НОД = 36

Сократим числитель и знаменатель дроби на 36 и получим ответ.

$${252over540} ={7over15}$$ – чтобы быстро сократить, достаточно посмотреть на разложение чисел.

Если 540=2*2*3*3*3*5, а НОД=36=2*2*3*3, то 540 = 36*3*5. И если мы поделим 540 на 36, то получим 3*5=15.

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

Заключение

Что мы узнали?

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

Тест по теме

Доска почёта

Доска почёта

Чтобы попасть сюда — пройдите тест.

    Пока никого нет. Будьте первым!

Оценка статьи

4.3

Средняя оценка: 4.3

Всего получено оценок: 224.


А какая ваша оценка?

Понравилась статья? Поделить с друзьями:
  • Как найти энергию системы колебаний
  • Как найти сумму координат точек пересечения графиков
  • Как найти максимальный делитель числа паскаль
  • Как найти витые пары
  • Как найти радиус окружности зная диаметр формула