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

Наибольший общий делитель (НОД) — это наибольшее натуральное число, на которое без остатка делятся все числа из данного набора. В математике НОД является фундаментальным понятием теории чисел, используемым для упрощения дробей, решения диофантовых уравнений и в криптографии. Для двух целых чисел \(a\) и \(b\) НОД обозначается как \(\gcd(a, b)\) (от англ. greatest common divisor) или \(\text{НОД}(a, b)\). Если НОД равен 1, числа называются взаимно простыми.

Определение и свойства

Формально, для целых чисел \(a\) и \(b\), не равных одновременно нулю, наибольший общий делитель определяется как наибольшее целое число \(d\), такое что \(d \mid a\) и \(d \mid b\) (символ \(\mid\) означает «делит»). Для нулевых чисел: \(\text{НОД}(a, 0) = |a|\), а \(\text{НОД}(0, 0)\) не определён (математически считается бесконечностью, но в алгоритмах обычно принимается за 0).

Основные свойства НОД:

• Коммутативность: \(\text{НОД}(a, b) = \text{НОД}(b, a)\).
• Ассоциативность: \(\text{НОД}(a, \text{НОД}(b, c)) = \text{НОД}(\text{НОД}(a, b), c)\).
• Дистрибутивность относительно умножения: \(\text{НОД}(ac, bc) = |c| \cdot \text{НОД}(a, b)\).
• Линейное представление (лемма Безу): существуют целые числа \(x\) и \(y\), такие что \(ax + by = \text{НОД}(a, b)\).

Методы вычисления

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

Классический школьный метод: разложить каждое число на простые множители, затем взять произведение общих множителей в минимальных степенях. Например, для чисел 12 и 18: \[ 12 = 2^2 \cdot 3,\quad 18 = 2 \cdot 3^2 \implies \text{НОД}(12, 18) = 2^1 \cdot 3^1 = 6. \] Метод эффективен для небольших чисел, но при больших значениях (например, 100-значных) разложение на множители становится вычислительно сложной задачей.

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

Наиболее распространённый метод, основанный на свойстве: \(\text{НОД}(a, b) = \text{НОД}(b, a \bmod b)\), где \(a \bmod b\) — остаток от деления \(a\) на \(b\). Процесс повторяется, пока остаток не станет равен нулю; последний ненулевой остаток и есть НОД. Пример для 48 и 18: \[ 48 \bmod 18 = 12,\quad 18 \bmod 12 = 6,\quad 12 \bmod 6 = 0 \implies \text{НОД}(48, 18) = 6. \] Алгоритм работает за \(O(\log \min(a, b))\) шагов, что делает его пригодным для чисел любой длины.

Бинарный алгоритм (алгоритм Стейна)

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

• Если оба числа чётные: \(\text{НОД}(a, b) = 2 \cdot \text{НОД}(a/2, b/2)\).
• Если одно чётное, другое нечётное: \(\text{НОД}(a, b) = \text{НОД}(a/2, b)\).
• Если оба нечётные: \(\text{НОД}(a, b) = \text{НОД}(|a - b|, \min(a, b))\).

Алгоритм Евклида с вычитанием

Исторически первая версия: вместо деления используется многократное вычитание меньшего числа из большего. Например, \(\text{НОД}(30, 12)\): \[ 30 - 12 = 18,\quad 18 - 12 = 6,\quad 12 - 6 = 6,\quad 6 - 6 = 0 \implies \text{НОД} = 6. \] Менее эффективен, чем деление с остатком, но нагляден для обучения.

Применение

Сокращение дробей

НОД используется для приведения дробей к несократимому виду: \(\frac{a}{b} = \frac{a / \text{НОД}(a, b)}{b / \text{НОД}(a, b)}\). Например, \(\frac{24}{36} = \frac{24 / 12}{36 / 12} = \frac{2}{3}\).

Решение диофантовых уравнений

Линейное диофантово уравнение \(ax + by = c\) имеет целые решения тогда и только тогда, когда \(c\) делится на \(\text{НОД}(a, b)\). Сами решения находятся с помощью расширенного алгоритма Евклида, который также даёт коэффициенты Безу.

Криптография

В криптосистеме RSA (разработана в 1977 году Роном Ривестом, Ади Шамиром и Леонардом Адлеманом) НОД используется для проверки взаимной простоты чисел при генерации ключей. Выбор открытого ключа \(e\) требует, чтобы \(\text{НОД}(e, \varphi(n)) = 1\), где \(\varphi(n)\) — функция Эйлера.

Теория колец

В абстрактной алгебре понятие НОД обобщается на евклидовы кольца, такие как кольцо многочленов \(F[x]\) над полем. Для многочленов НОД определяется как многочлен наибольшей степени, делящий оба многочлена.

НОД для более чем двух чисел

НОД для набора чисел \(a_1, a_2, \dots, a_n\) вычисляется рекурсивно: \[ \text{НОД}(a_1, a_2, \dots, a_n) = \text{НОД}(\text{НОД}(a_1, a_2, \dots, a_{n-1}), a_n). \] Например, \(\text{НОД}(12, 18, 24) = \text{НОД}(\text{НОД}(12, 18), 24) = \text{НОД}(6, 24) = 6\).

Связь с наименьшим общим кратным

Для двух чисел \(a\) и \(b\) выполняется соотношение: \[ \text{НОД}(a, b) \cdot \text{НОК}(a, b) = |a \cdot b|, \] где \(\text{НОК}\) — наименьшее общее кратное. Это позволяет вычислить одно через другое.

Историческая справка

Понятие наибольшего общего делителя известно с античных времён. Алгоритм Евклида описан в «Началах» Евклида (около 300 г. до н. э.) в книгах VII и X. В Древнем Китае аналогичный метод использовался в трактате «Математика в девяти книгах» (II век до н. э.). В Средние века алгоритм изучался арабскими математиками, такими как аль-Хорезми. Современное обозначение \(\gcd\) ввёл Леонард Эйлер в XVIII веке.

Интересные факты

• НОД нуля и любого числа равен модулю этого числа: \(\text{НОД}(0, 7) = 7\).
• Два числа называются взаимно простыми, если их НОД равен 1. Например, 8 и 15.
• Понятие НОД обобщается на рациональные числа: \(\text{НОД}(a/b, c/d) = \text{НОД}(a, c) / \text{НОК}(b, d)\).
• В криптографии с открытым ключом алгоритм Евклида используется для нахождения обратного элемента по модулю.

Источники

• Виноградов И. М. «Основы теории чисел». — М.: Наука, 1972.
• Кнут Д. Э. «Искусство программирования». Том 2. — М.: Вильямс, 2007.
• Hardy G. H., Wright E. M. «An Introduction to the Theory of Numbers». — Oxford University Press, 2008.
• «Энциклопедия элементарной математики» под ред. П. С. Александрова. — М.: ГИТТЛ, 1951.