Что такое НОД чисел

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

$\gcd(a,b) = \gcd(b,\ a \bmod b)$

Разбор по случаям

Примеры

Разложение на множители: 24 и 36. Раскладываем оба числа на простые множители: $24 = 2^3 \cdot 3$ и $36 = 2^2 \cdot 3^2$. Общие простые множители — это 2 и 3, каждый берём в наименьшей из встретившихся у двух чисел степеней: $2^2$ и $3^1$.

Перемножаем эти степени и получаем: $\gcd(24,36) = 2^2 \cdot 3 = 12$.

Значит, наибольшее натуральное число, на которое делятся без остатка и 24, и 36 сразу, равно двенадцати.

Алгоритм Евклида: 17 и 45. Число 17 простое и делится только на себя и на единицу, а 45 на 17 без остатка не делится. Проверка по алгоритму Евклида подтверждает результат: $45 = 2 \cdot 17 + 11$, затем $17 = 1 \cdot 11 + 6$, далее $11 = 1 \cdot 6 + 5$, потом $6 = 1 \cdot 5 + 1$ и наконец $5 = 5 \cdot 1 + 0$. Значит, $\gcd(17,45) = 1$ — числа взаимно простые, общих делителей, кроме единицы, у них нет вовсе.

Частые ошибки

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

Коротко

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