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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так, в задаче (НОД(45; 60) = 15).

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

48=2⋅2⋅2⋅2⋅3=24⋅3;36=2⋅2⋅3⋅3=22⋅32;НОД(48;36)=22⋅3=12.

Признак делимости на произведение взаимно простых чисел:

Была ли эта статья полезной?

Как найти НОД

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

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

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

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

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

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

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

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

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

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

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

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

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

Любое натуральное число всегда делится на 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) называются
делителями числа.

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

Обратите внимание, что числа 12 и
36 имеют общие делители.
Это числа: 1, 2, 3, 4, 6, 12.
Наибольший из делителей этих чисел — 12.

Общий делитель двух данных чисел «a» и «b» — это число, на которое делятся без остатка
оба данных числа «a» и «b».

Пример: НОД (12; 36) = 12.

Делители чисел в записи решения обозначают большой буквой «Д».

Пример.

Д (7) = {1, 7}

Д (9) = {1, 9}

НОД (7; 9) = 1

Числа
7 и 9 имеют
только один общий делитель — число 1.
Такие числа называют взаимно простыми числами.

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

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

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

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

Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

1. Подчёркиваем одинаковые простые множители в обоих числах.
   
   28 = 2 · 2 · 7

   64 = 2 · 2 · 2 · 2 · 2 · 2

2. Находим произведение одинаковых простых множителей и записать ответ;
   
   НОД (28; 64) = 2 · 2 = 4

   Ответ: НОД (28; 64) = 4

Оформить нахождение НОД можно двумя способами:
в столбик (как делали выше) или «в строчку».

Первый способ записи НОД

Найти НОД 48 и 36.

НОД (48; 36) = 2 · 2 · 3 = 12

Второй способ записи НОД

Теперь запишем решение поиска НОД в строчку. Найти НОД 10 и 15.

Д (10) = {1, 2, 5, 10}

Д (15) = {1, 3, 5, 15}

Д (10, 15) = {1, 5}

НОД (10; 15) = 5

Ваши комментарии

Оставить комментарий: