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

27 мая 2023
6 минут
7 472

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

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

Алгоритм Евклида для нахождения НОД

Алгоритм Евклида позволяет с легкостью вычислить наибольший общий делитель для двух положительных чисел. Формулировки и доказательство алгоритма Евклида мы привели в разделе «Наибольший общий делитель: определитель, примеры».

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

$a = b \cdot q_{1} + r_{1}, 0 < r_{1} < b b = r_{1} \cdot q_{2} + r_{2}, 0 < r_{2} < r_{1} r_{1} = r_{2} \cdot q_{3} + r_{3}, 0 < r_{3} < r_{2} r_{2} = r_{3} \cdot q_{4} + r_{4}, 0 < r_{4} < r_{3} ⋮ r_{k - 2} = r_{k - 1} \cdot q_{k} + r_{k}, 0 < r_{k} < r_{k - 1} r_{k - 1} = r_{k} \cdot 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 \cdot 3 + 99, 111 = 99 \cdot 1 + 12, 99 = 12 \cdot 8 + 3, 12 = 3 \cdot 4$ .

Таким образом, наибольший общий делитель чисел $111$ и $432$ – это $3$ .

Ответ: НОД $(111, 432) = 3$ .

Пример 3

Найдите наибольший общий делитель чисел $661$ и $113$ .

Решение

Проведем последовательно деление чисел и получим НОД $(661, 113) = 1$ . Это значит, что $661$ и $113$ – это взаимно простые числа. Мы могли выяснить это до начала вычислений, если бы обратились к таблице простых чисел.

Ответ: НОД $(661, 113) = 1$ .

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

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

Пример 4

Если мы разложим числа $220$ и $600$ на простые множители, то получим два произведения: $220 = 2 \cdot 2 \cdot 5 \cdot 11$ и $600 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \cdot 5$ . Общими в этих двух произведениях будут множители $2, 2$ и $5$ . Это значит, что НОД $(220, 600) = 2 \cdot 2 \cdot 5 = 20$ .

Пример 5

Найдите наибольший общий делитель чисел $72$ и $96$ .

Решение

Найдем все простые множители чисел $72$ и $96$ :

$\begin{matrix} 72 \\ 36 \\ 18 9 3 1 \end{matrix} \begin{matrix} 2 2 2 \\ 3 \\ 3 \end{matrix}$

$\begin{matrix} 96 \\ 48 \\ 24 12 6 3 1 \end{matrix} \begin{matrix} 2 2 2 \\ 2 \\ 2 3 \end{matrix}$

Общими для двух чисел простые множители: $2, 2, 2$ и $3$ . Это значит, что НОД $(72, 96) = 2 \cdot 2 \cdot 2 \cdot 3 = 24$ .

Ответ: НОД $(72, 96) = 24$ .

Правило нахождения наибольшего общего делителя двух чисел основано на свойствах наибольшего общего делителя, согласно которому НОД $(m \cdot a_{1}, m \cdot b_{1}) = m \cdot$ НОД $(a_{1}, b_{1})$ , где $m$ – любое целое положительное число.

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

Независимо от количества чисел, для которых нам нужно найти НОД, мы будем действовать по одному и тому же алгоритму, который заключается в последовательном нахождении НОД двух чисел. Основан этот алгоритм на применении следующей теоремы: НОД нескольких чисел $a_{1}, a_{2}, \dots, a_{k}$ равен числу $d_{k}$ , которое находится при последовательном вычислении НОД $(a_{1}, a_{2}) = d_{2}$ , НОД $(d_{2}, a_{3}) = d_{3}$ , НОД $(d_{3}, a_{4}) = d_{4}$ , $\dots$ , НОД $(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 \cdot 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$ .

Ответ: НОД $(78, 294, 570, 36) = 6$ .

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

Пример 7

Вычислите НОД чисел $78, 294, 570$ и $36$ .

Решение

Произведем разложение данных чисел на простые множители: $78 = 2 \cdot 3 \cdot 13, 294 = 2 \cdot 3 \cdot 7 \cdot 7, 570 = 2 \cdot 3 \cdot 5 \cdot 19, 36 = 2 \cdot 2 \cdot 3 \cdot 3$ .

Для всех четырех чисел общими простыми множителями будут числа $2$ и $3$ .

Получается, что НОД $(78, 294, 570, 36) = 2 \cdot 3 = 6$ .

Ответ: НОД $(78, 294, 570, 36) = 6$ .

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

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

Пример 8

Найдите НОД отрицательных целых чисел $- 231$ и $- 140$ .

Решение

Для выполнения вычислений возьмем модули чисел, данных в условии. Это будут числа $231$ и $140$ . Запишем это кратко: НОД $(- 231, - 140) =$ НОД $(231, 140)$ . Теперь применим алгоритм Евклида для нахождения простых множителей двух чисел: $231 = 140 \cdot 1 + 91; 140 = 91 \cdot 1 + 49; 91 = 49 \cdot 1 + 42; 49 = 42 \cdot 1 + 7$ и $42 = 7 \cdot 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 \cdot 3 \cdot 5 \cdot 13, 81 = 3 \cdot 3 \cdot 3 \cdot 3$ и $189 = 3 \cdot 3 \cdot 3 \cdot 7$ . Общими для трех чисел являются простые множители $3$ и $3$ . Получается , что НОД $(585, 81, 189) =$ НОД $(- 585, 81, - 189) = 9$ .

Ответ: НОД $(- 585, 81, - 189) = 9$ .