Введение

Наибольшее целое число, делящее заданные целые числа
В математике наибольший общий делитель (НОД) двух или более целых чисел, не являющихся все нулевыми, — это наибольшее положительное целое число, которое делит каждое из этих чисел. Для двух целых чисел x и y наибольший общий делитель x и y обозначается. Например, НОД(8, 12) = 4, то есть 1=gcd(8, 12) = 4. В названии "наибольший общий делитель" прилагательное "наибольший" может быть заменено на "наивысший", а слово "делитель" — на "фактор", поэтому другие названия включают наибольший общий фактор и т. д. Исторически для обозначения этого понятия использовались также термины "наибольшая общая мера". Это понятие можно расширить на полиномы (см. Наибольший общий делитель полиномов) и другие коммутативные кольца (см. ниже).

Определение

Наибольший общий делитель (GCD) целых чисел a и b, по крайней мере одно из которых отлично от нуля, — это наибольшее положительное целое число d, такое, что d является делителем как a, так и b; то есть, существуют целые числа e и f, для которых a = de и b = df, и d — наибольшее такое число. GCD чисел a и b обычно обозначается gcd(a, b). Некоторые авторы используют обозначение (a, b), эта конвенция распространена во многих системах компьютерной алгебры. Однако некоторые авторы оставляют gcd(0, 0) неопределённым. GCD чисел a и b является их наибольшим положительным общим делителем в отношении порядка делимости. Это означает, что общие делители a и b — это ровно делители их GCD. Это обычно доказывается с использованием леммы Евклида, основной теоремы арифметики или алгоритма Евклида. Именно в этом смысле используется понятие "наибольший" при обобщениях концепции GCD.

Копримные числа

Два числа называются относительно простыми или сопростыми, если их наибольший общий делитель равен 1. Например, 9 и 28 являются взаимно простыми.

Геометрический вид

Например, прямоугольную область размером 24 на 60 можно разделить на сетку из квадратов размером 1 на 1, 2 на 2, 3 на 3, 4 на 4, 6 на 6 или 12 на 12. Следовательно, 12 является наибольшим общим делителем чисел 24 и 60. Таким образом, прямоугольную область размером 24 на 60 можно разделить на сетку из квадратов размером 12 на 12, при этом вдоль одной стороны будет два квадрата (24 / 12 = 2), а вдоль другой – пять квадратов (60 / 12 = 5).

Редукционные фракции

Наибольший общий делитель полезен для сокращения дробей до несократимого вида. Например, gcd(42, 56) = 14, следовательно,

Алгоритм GCD Лемера

Алгоритм Лемера основан на наблюдении, что начальные частные, получаемые алгоритмом Евклида, могут быть определены, используя только несколько первых цифр; это особенно полезно для чисел, превышающих размер компьютерного слова. По сути, извлекаются начальные цифры, обычно формирующие одно или два компьютерных слова, и на этих меньших числах выполняется алгоритм Евклида, пока гарантируется, что частные будут такими же, как при использовании исходных чисел. Эти частные собираются в небольшую матрицу преобразования 2x2 (матрицу целых чисел, представленных одним словом), чтобы уменьшить исходные числа. Этот процесс повторяется до тех пор, пока числа не станут достаточно малыми для более эффективного применения бинарного алгоритма (см. ниже). Этот алгоритм повышает скорость, поскольку уменьшает количество операций с очень большими числами и позволяет использовать аппаратную арифметику для большинства вычислений. Фактически, большинство частных очень малы, поэтому значительное количество шагов алгоритма Евклида можно представить в матрице 2x2, состоящей из целых чисел, представленных одним словом. Если алгоритм Лемера сталкивается с частным, которое слишком велико, он должен вернуться к одной итерации алгоритма Евклида с выполнением деления больших чисел.

Сложность

Комплексность вычислений наибольших общих делителей широко изучена. Если использовать алгоритм Евклида и элементарные алгоритмы умножения и деления, вычисление наибольшего общего делителя двух целых чисел, содержащих не более n бит, имеет сложность O(n²). Это означает, что вычисление наибольшего общего делителя, до постоянного множителя, имеет такую же сложность, как и умножение. Однако, если используется алгоритм быстрого умножения, можно модифицировать алгоритм Евклида для улучшения сложности, но вычисление наибольшего общего делителя становится медленнее, чем умножение. Более точно, если умножение двух целых чисел, содержащих n бит, занимает время T(n), то самый быстрый из известных алгоритмов для вычисления наибольшего общего делителя имеет сложность O(T(n) log n). Следовательно, самый быстрый из известных алгоритмов имеет сложность O(n (log n)²). Предыдущие оценки сложности справедливы для стандартных моделей вычислений, в частности, многоленточных машин Тьюринга и машин с произвольным доступом к памяти. Таким образом, вычисление наибольших общих делителей относится к классу задач, разрешимых за квазилинейное время. А следовательно, соответствующая задача принятия решений относится к классу P задач, разрешимых за полиномиальное время. Неизвестно, принадлежит ли задача GCD классу NC, и, следовательно, не существует известных способов эффективно её распараллелить; также неизвестно, является ли она NP-полной, что означало бы малую вероятность эффективной параллелизации вычислений GCD. Шалкросс и др. показали, что связанная задача (EUGCD, определение последовательности остатков, возникающих в процессе выполнения алгоритма Евклида) является NC-эквивалентной задаче целочисленного линейного программирования с двумя переменными; если одна из этих задач принадлежит классу NC или является NP-полной, то другая тоже. Поскольку NC содержит NL, также неизвестно, существует ли алгоритм вычисления GCD, эффективный по памяти, даже для недетерминированных машин Тьюринга. Хотя задача не принадлежит классу NC, существуют параллельные алгоритмы, асимптотически более быстрые, чем алгоритм Евклида; самый быстрый известный детерминированный алгоритм принадлежит Чору и Голдрейху, который (в модели CRCW PRAM) может решить задачу за время O(n/log n) с использованием n^(1+ε) процессоров. Случайные алгоритмы могут решить задачу за время O((log n)²) на процессорах (что является суперполиномиальной сложностью).

Вероятности и ожидаемая стоимость

В 1972 году Джеймс Э. Найманн показал, что k целых чисел, выбранных независимо и равномерно из , являются взаимно простыми с вероятностью 1/ζ(k) при n стремящемся к бесконечности, где ζ обозначает дзета-функцию Римана. (См. статью «Взаимно простые» для вывода.) Этот результат был расширен в 1987 году, чтобы показать, что вероятность того, что k случайных целых чисел имеют наибольший общий делитель d, равна d^(-k)/ζ(k). Используя эту информацию, можно увидеть (неформально), что математическое ожидание функции наибольшего общего делителя не существует при k = 2. В этом случае вероятность того, что НОД равен d, равна d^(-2)/ζ(2), и поскольку ζ(2) = π^(2)/6, мы имеем:

Это последнее суммирование представляет собой гармонический ряд, который расходится. Однако, когда k ≥ 3, математическое ожидание определено однозначно, и, согласно вышеприведенному аргументу, оно равно:

Для k = 3 это приблизительно равно 1,3684. Для k = 4 это приблизительно равно 1,1106.