Как найти минимальный общий делитель

Для этого термина существует аббревиатура «НОД», которая имеет и другие значения, см. Нод.

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей[1]. Пример: для чисел 54 и 24 наибольший общий делитель равен 6.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не равно нулю.

Возможные обозначения наибольшего общего делителя чисел m и n:

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.

Связанные определения[править | править код]

Наименьшее общее кратное[править | править код]

Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n (без остатка). Обозначается НОК(m,n) или [m,n], а в английской литературе {mathrm  {lcm}}(m,n).

НОК для ненулевых чисел m и n всегда существует и связан с НОД следующим соотношением:

(m,n)cdot [m,n]=mcdot n

Это частный случай более общей теоремы: если a_{1},a_{2},dots ,a_{n} — ненулевые числа, D — какое-либо их общее кратное, то имеет место формула:

D=[a_{1},a_{2},dots ,a_{n}]cdot left({frac  {D}{a_{1}}},{frac  {D}{a_{2}}},dots ,{frac  {D}{a_{n}}}right)

Взаимно простые числа[править | править код]

Числа m и n называются взаимно простыми, если у них нет общих делителей, кроме pm 1. Для таких чисел НОД{displaystyle (m,n)=1}. Обратно, если НОД{displaystyle (m,n)=1,} то числа взаимно просты.

Аналогично, целые числа a_{1},a_{2},dots a_{k}, где kgeq 2, называются взаимно простыми, если их наибольший общий делитель равен единице.

Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.

Способы вычисления[править | править код]

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.

Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел m и n на простые множители:

n=p_{1}^{{d_{1}}}cdot dots cdot p_{k}^{{d_{k}}},
m=p_{1}^{{e_{1}}}cdot dots cdot p_{k}^{{e_{k}}},

где p_{1},dots ,p_{k} — различные простые числа, а d_{1},dots ,d_{k} и e_{1},dots ,e_{k} — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(n,m) и НОК[n,m] выражаются формулами:

(n,m)=p_{1}^{{min(d_{1},e_{1})}}cdot dots cdot p_{k}^{{min(d_{k},e_{k})}},
[n,m]=p_{1}^{{max(d_{1},e_{1})}}cdot dots cdot p_{k}^{{max(d_{k},e_{k})}}.

Если чисел более двух: a_{1},a_{2},dots a_{n}, их НОД находится по следующему алгоритму:

d_{2}=(a_{1},a_{2})
d_{3}=(d_{2},a_{3})

………
d_{n}=(d_{{n-1}},a_{n}) — это и есть искомый НОД.

Свойства[править | править код]

  • Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
  • Если m делится на n, то НОД(m, n) = n. В частности, НОД(n, n) = n.
  • {displaystyle (a,b)=(a-b,b)}. В общем случае, если {displaystyle a=b*q+c}, где {displaystyle a,b,c,q} – целые числа, то {displaystyle (a,b)=(b,c)}.
  • (acdot m,acdot n)=|a|cdot (m,n) — общий множитель можно выносить за знак НОД.
  • Если D=(m,n), то после деления на D числа становятся взаимно простыми, то есть, left({{frac  {m}{D}},{frac  {n}{D}}}right)=1. Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
  • Мультипликативность: если a_{1},a_{2} взаимно просты, то:
(a_{1}cdot a_{2},b)=(a_{1},b)cdot (a_{2},b)
left{acdot m+bcdot nmid a,bin mathbb{Z } right}
и поэтому (m,n) представим в виде линейной комбинации чисел m и n:

(m,n)=ucdot m+vcdot n.
Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы mathbb {Z} , порождённая набором {a_{1},a_{2},dots ,a_{n}}, — циклическая и порождается одним элементом: НОД(a1, a2, … , an).

Вариации и обобщения[править | править код]

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

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

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

НОД двух элементов коммутативного кольца, вообще говоря, не обязан существовать. Например, для нижеследующих элементов a и b кольца {mathbb  {Z}}left[{sqrt  {-3}}right] не существует наибольшего общего делителя:

a=4=2cdot 2=left(1+{sqrt  {-3}}right)left(1-{sqrt  {-3}}right),qquad b=left(1+{sqrt  {-3}}right)cdot 2.

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

См. также[править | править код]

  • Бинарный алгоритм вычисления НОД
  • Делимость
  • Алгоритм Евклида
  • Наименьшее общее кратное

Литература[править | править код]

  • Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Примечания[править | править код]

  1. Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3. страница 857

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

Источник: https://w7.pngwing.com/pngs/261/1019/png-transparent-two-children-writing-on-chalkboard-illustration-teacher-mathematics-estudante-math-class-teacher-and-student-child-class-text.png
Источник: https://w7.pngwing.com/pngs/261/1019/png-transparent-two-children-writing-on-chalkboard-illustration-teacher-mathematics-estudante-math-class-teacher-and-student-child-class-text.png

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

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

Что такое НОД и НОК: вспомните математику 6 класса ?

Последняя строчка – особенная, ведь из неё следует, что числа 9 и 16 не имеют общих делителей, кроме 1. Такие числа называются взаимно простыми.

  • Ввел это понятие Евклид, авторству которого принадлежит теорема о бесконечности простых чисел, которую, например, Г.Г. Харди в своей “Апологии математики” причисляет к красивейшим плодам чистой математики.

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

Если НОД “подпирает” числа a и b снизу, то наименьшее общее кратное – наоборот, является наименьшим числом, которое делится на a и b без остатка. Пример:

Что такое НОД и НОК: вспомните математику 6 класса ?

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

Естественно, НОК И НОД определены и более, чем для двух чисел

Алгоритмы нахождения

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

Чтобы найти НОК и НОд как раз необходимо это знать каноническое разложение чисел a и b. Давайте разберем на примере чисел 42 и 188, которые уже на “глазок” не раскусить. Итак:

Что такое НОД и НОК: вспомните математику 6 класса ?

Исходя из этого разложения существует простая формула:

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

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

Здесь, описка: вместо НОК написан НОД. Вручную подбор бы затянулся
Здесь, описка: вместо НОК написан НОД. Вручную подбор бы затянулся

Как видно, процесс вычисления НОК и НОД требует проведения подготовительного этапа – факторизации, который для больших чисел уже не является тривиальной задачей. Однако, к счастью, для более эффективного вычисления НОД (а, значит, и НОК, ведь их можно выразить друг через друга) еще Евклидом был придуман особый алгоритм. названный его именем. Этот алгоритм по праву считается золотым достоянием математики. О нём поговорим в одной из следующих заметок. Спасибо за внимание!

Читайте также:

  • Что такое вероятность: взрослому и ребенку
  • Простое объяснение пропорций
  • TELEGRAM и Facebook – там я публикую не только интересные статьи, но и математический юмор и многое другое.

План урока:

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

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

Минутка истории

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

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

Например:

В городском парке проводился ежегодный марафон. Для участия в марафоне пришло 36 мальчиков, 24 девочки. По условиям соревнования, всех участников необходимо поделить на команды, в которые войдут  и мальчики, и девочки. Сколько одинаковых команд можно сформировать из данного количества детей?

erer

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

Выполним необходимые вычисления – определим существующие множители. Вычисления запишем в столбик.

Начнем с 36.

2

36 | 2

18

Полученное частное – 18, оно четное. Делитель остается прежним:

36 | 2

18 | 2

9

9 – нечетное, поэтому берем следующий делитель – 3:

36 | 2

18 | 2

9  | 3

3

Частное – простое числовое значение, делится само на себя:

36 | 2

18 | 2

9  | 3

3  | 3

1

Частное – единица, разложение окончено.

Выпишем составляющие:

36 = 2×2×3×3

Переходим к 24.

24 заканчивается четной цифрой, значит, кратно двум:

242

12

Делитель оставляем прежним, частное 12 – четное:

242

122

6

Результат деления 6, снова делим на 2:

24 | 2

12 | 2

6  | 2

3

Получили простое числовое значение, которое делится само на себя:

24 | 2

12 | 2

6  | 2

3  | 3

1

Разложение окончено. Запишем полученные компоненты:

24 = 2 × 2 × 2 × 3.

В финале выполненных вычислений мы получили:

36 = 2 × 2 × 2 × 3× 3;

24 = 2 × 2 × 2 × 3.

Давайте выберем одинаковые составляющие. Видно, что в каждом выражении такими составляющими будут: 2 ×2 × 3.

Перемножим выделенные компоненты:

2 ×2 × 3 = 12.

12 – самое большое числовое значение, на которое можно разделить оба делимых.

Мы выяснили, что всех участников можно распределить на 12 одинаковых команд.

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

3

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

4

Выполним задание.

Определите НОД (наибольший общий делитель) 66 и 44.

Чтобы выполнить задание будем придерживаться рассмотренного алгоритма действий.

Определим компоненты, входящие в состав числового значения.

5

Значит:

66 | 2

33

Результат деления оканчивается нечетной цифрой, проверяем по признакам делимости на 3:

6

66 | 2

33 | 3

11

Мы получили простое числовое значение

7

66 | 2

33 | 3

11 | 11

 1

     В итоге вычислений – 1, разложение окончено.

Переходим ко второму известному значению.

  • 1) Определим составляющие, входящие в состав:

Проверяем по признакам делимости. Данное числовое значение заканчивается четной цифрой, значит, оно делится на 2.

44 | 2

          22

Частное снова делится на 2:

          44 | 2    

          22 | 2

          11

В результате простое число, делим само на себя:

44 | 2    

22 | 2

11 | 11

1

Разложение окончено.

  • 2) Выпишем компоненты обоих делимых, определим одинаковые:

66 = 2 × 3 × 11

44 = 2 ×2 × 11

  • 3) Перемножим выделенные составляющие:

2 × 11=22

Выходит, что наибольший общий делитель – 22.

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

НОД (66;44) = 22.

Разберем задачу

Выпускники на праздник последнего звонка, приготовили цветы своим учителям. Они принесли 69 роз и 46 гладиолусов и разделили поровну между всеми учителями. Сколько учителей поздравили выпускники?

8

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

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

  • 1) Разложим на составляющие:

69 | 3               46 | 2

23 | 23             23 | 23

1                       1

  • 2) Выберем общее числовое значение находящееся в составляющих :

69 = 3 × 23

46 = 2 × 23.

Нам подходит только  23.

НОД (69;46) = 23.

Наибольшим общим делителем для данных чисел будет 23. 

Выпускники поздравили 23 учителя.

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

Рассмотрим ситуацию.

В первой банке лежало 9 декоративных камней, во второй – 14 . Сколько  предметов интерьера, можно украсить  имеющимся материалом, если на каждое изделие использовать равное, при этом, наибольшее количество,камней из первой и второй коробки?

9

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

14 | 2             9 | 3

 7  | 7             3 | 3

 1                   1

Выписываем компоненты, входящие в состав известных значений:

14 = 2 × 7

9 = 3 × 3

 Повторяющихся составляющих нет. Мы знаем, если любое натуральное число  умножить на 1, числовое значение не изменится. Значит, единственный, наибольший общий множитель чисел – 1.

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

 В арифметике числа, наибольшим общим множителем которых является 1, называют взаимно простыми.

10

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

14 | 2             9 | 3

 7  | 7             3 | 3

 1                   1

Выписываем компоненты, входящие в состав известных значений:

14 = 2 × 7

9 = 3 × 3

 Повторяющихся составляющих нет. Мы знаем, если любое натуральное число  умножить на 1, числовое значение не изменится. Значит, единственный, наибольший общий множитель чисел – 1.

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

 В арифметике, числа, наибольшим общим множителем которых является 1, называют взаимно простыми

11

Чтобы ответить на главный вопрос задачи, необходимо определить самое маленькое числовое значение, которое будет, без остатка делиться на 4, на 5, то есть будет кратно 4, 5.

Сначала, подберем значения, кратные четырем: 4,8,12,16,20,24,28.

Теперь, значения, кратные пяти: 5,10,15,20,25,30.

После этого, необходимо найти самое маленькое число, которое будет кратным 4, 5 одновременно.

Из перечисленных числовых значений,  подходит только 20. Оно делится без остатка на 4, на 5. Наименьшим общим кратным двух чисел будет 20.

Важно!

12

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

13

Например:

Вычислим НОК для 30 и 32.

Чтобы выполнить нужные вычисления воспользуемся алгоритмом нахождения НОК.

14ris

Разберем задачу

В городе Москва, для  качественной съемки парада, приуроченного к празднику 9 Мая, организаторы подготовили квадрокоптеры с видеокамерами. Из одной точки  одновременно, будут запущены три аппарата. Время полета первого 8 минут, второго – 12.Через какое время,квадрокоптеры снова будут запущены одновременно, если по возвращению в точку запуска им меняют батарею и сразу отправляют назад.

15

Чтобы получить ответ на главный вопрос задачи, найдем наименьшее числовое значение, кратное двум данным величинам.

Для этого будем использовать рассмотренный алгоритм:

16ris

Квадрокоптеры будут одновременно запущены через 24 минуты.

Последняя задачка  на внимательность.

На уроке Ваня около доски выполнял задание. Он написал: НОК (25; 115) = 100. Подскажите Ване, верно ли он выполнил задание (не выполняя вычислений)?

17

Вначале, давайте вспомним определение НОК:

18

Из определения следует, НОК нацело делится на известные данные. Однако,видим, что 100 на 115 нацело разделить невозможно. Поэтому Ваня, допустил ошибку в своих расчетах!

Вот так легко и просто можно решить огромное количество задач, даже не совершая сложных вычислений!

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

Минутка истории

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

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

3. Результат суммирования  цифр числа 18, в два раза меньше этого числа. Существует только одно число такого плана.

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

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

Наибольший общий делитель (НОД)

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

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

Если натуральное число a делится на натуральное число bb, то bb называют делителем числа aa, а число aa называют кратным числа bb. aa и bb являются натуральными числами. Число gg называют общим делителем и для aa и для bb. Множество общих делителей чисел aa и bb конечно, так как ни один из этих делителей не может быть больше, чем aa. Значит, среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел aa и bb и для его обозначения используют записи: НОД (a;b)(a;b) или D(a;b)(a;b)

Пример
Наибольший общий делитель (НОД) чисел 1818 и 2424 — это 66.

Как найти наибольший общий делитель (НОД)

Существует несколько способов нахождения наибольшего общего делителя (НОД) двух или более целых чисел:

  • Алгоритм Евклида: НОД(a,b)=(a, b) = НОД (b,a(b, a mod b)b), где «mod» – это операция взятия остатка от деления большего числа на меньшее. Этот алгоритм можно продолжать до тех пор, пока одно из чисел не станет равно нулю. В этом случае НОД равен ненулевому числу.

Пример
НОД(18,24)=НОД(24,18)=НОД(18,6)=НОД(6,0)=6НОД(18, 24) = НОД(24, 18) = НОД(18, 6) = НОД(6, 0) = 6

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

Пример
НОД(60,84)=22⋅31=12(60, 84) = 2^{2} cdot 3^{1} = 12, так как общие простые множители −2- 2 и 33, их минимальные степени −2- 2 и 11 соответственно.

  • Таблица делителей: Составить таблицы всех делителей каждого числа и найти наибольшее общее число, которое является делителем обоих чисел. Этот метод не рекомендуется для больших чисел, так как он требует много времени и усилий.

Наименьшее общее кратное (НОК)

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

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

Общими кратными чисел называются числа которые делятся на исходные без остатка. Например для чисел 2525 и 5050 общими кратными будут числа 50,100,150,20050,100,150,200 и т.д Наименьшее из общих кратных будет называться НОК и обозначается НОК(a;b)(a;b) или K(a;b).(a;b).

Пример
Наименьшее общее кратное чисел 88 и 1212 – это 2424. Т.е. НОК (8,12)=24(8, 12) = 24.

Как найти наименьшее общее кратное (НОК)

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

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

Пример
Рассмотрим два числа: 88 и 1212. Найдем их НОКНОК:

  • Разложим 88 и 1212 на простые множители: 8=23,12=22⋅38 = 2^3, 12 = 2^2 cdot 3.
  • Выпишем все простые множители: 23⋅32^3 cdot 3.
  • Для каждого простого множителя выберем наибольшую кратность: 232^3 и 33.
  • Умножим выбранные простые множители между собой: 23⋅3=242^3 cdot 3 = 24.

Таким образом, НОК чисел 88 и 1212 равен 2424.

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

  • Любое общее кратное чисел aa и bb делится на K(a;b)(a;b);
  • Если a⋮bavdots b , то К(a;b)=a(a;b)=a;
  • Если К(a;b)=k(a;b)=k и mm-натуральное число, то К(am;bm)=km(am;bm)=km. Если dd-общий делитель для aa и bb,то К(ad;bdfrac{a}{d};frac{b}{d})= kd frac{k}{d}
  • Если a⋮cavdots c и b⋮cbvdots c ,то abcfrac{ab}{c} – общее кратное чисел aa и bb;
  • Для любых натуральных чисел aa и bb выполняется равенство D(a;b)⋅К(a;b)=abD(a;b)cdot К(a;b)=ab;
  • Любой общий делитель чисел aa и bb является делителем числа D(a;b)D(a;b).

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

Содержание:

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

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

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

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

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

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

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