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

В математике , то наибольший общий делитель ( НОД ) двух или более целых чисел , которые не все равны нулю, является самым большим положительным целым числом , которое делит каждый из целых чисел. Для двух целых чисел x , y обозначается наибольший общий делитель x и y . Например, НОД 8 и 12 равны 4, то есть . ^{[1] [2] [3]}${\ Displaystyle \ НОД (х, у)}$${\ displaystyle \ gcd (8,12) = 4}$

В названии «наибольший общий делитель» прилагательное «наибольший» может быть заменено на «наивысший», а слово «делитель» может быть заменено на «фактор», чтобы другие имена включали наибольший общий делитель ( gcf ) и т. Д. ^{[4] [5] [6] [7]} Исторически, другие названия одного и того же понятия включали в себя наибольшую общую меру . ^[8]

Это понятие может быть расширено на многочлены (см. Наибольший общий делитель полиномов ) и другие коммутативные кольца (см. Раздел «В коммутативных кольцах» ниже).

Обзор [ править ]

Определение [ править ]

Наибольший общий делитель (НОД) двух ненулевых целых чисел через и Ь является наибольшим положительным целым числом d таким образом, что d является делителем обоих а и б ; то есть существуют целые числа e и f такие, что a = de и b = df , а d - наибольшее такое целое число. НОД для a и b обычно обозначается gcd ( a , b ) .^[9]

Это определение также применяется, когда одно из a и b равно нулю. В этом случае НОД - это абсолютное значение ненулевого целого числа: НОД ( a , 0) = НОД (0, a ) = | а | . Этот случай важен как завершающий шаг алгоритма Евклида .

Приведенное выше определение не может использоваться для определения gcd (0, 0) , так как 0 × n = 0 , и, таким образом, ноль не имеет наибольшего делителя. Однако ноль является его собственным наибольшим делителем, если наибольшее значение понимается в контексте отношения делимости, поэтому gcd (0, 0) обычно определяется как 0. Это сохраняет обычные тождества для GCD и, в частности, тождество Безу , а именно, что gcd ( a , b ) порождает тот же идеал, что и { a , b } . ^{[10] [11] [12]}Этому соглашению придерживаются многие системы компьютерной алгебры . ^[13] Тем не менее, некоторые авторы оставляют gcd (0, 0) неопределенным. ^[14]

НОД и б является их наибольшим общим положительным делителем в порядке отношении частичного из делимости . Это означает, что общие делители a и b в точности делят их НОД. Обычно это доказывается с помощью леммы Евклида , основной арифметической теоремы или алгоритма Евклида . Это значение слова «величайший», которое используется для обобщения концепции НОД.

Пример [ править ]

Число 54 можно выразить как произведение двух целых чисел несколькими способами:

${\ Displaystyle 54 \ раз 1 = 27 \ раз 2 = 18 \ раз 3 = 9 \ раз 6.}$

Таким образом, полный список делителей 54 равен . Аналогично делители 24 равны . Общие числа этих двух списков являются общими делителями 54 и 24, то есть${\ displaystyle 1,2,3,6,9,18,27,54}$${\ displaystyle 1,2,3,4,6,8,12,24}$

${\ displaystyle 1,2,3,6.}$

Из них наибольшее число равно 6, так что это наибольший общий делитель :

${\ displaystyle \ gcd (54,24) = 6.}$

Вычисление всех делителей двух чисел таким способом обычно неэффективно, особенно для больших чисел, у которых много делителей. Более эффективные методы описаны в § Расчет .

Номера Coprime [ править ]

Два числа называются взаимно простыми или взаимно простыми , если их наибольший общий делитель равен 1. ^[15] Например, 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).

Приложения [ править ]

Уменьшение дробей [ править ]

Наибольший общий делитель используется для сокращения дробей до наименьших членов . ^[16] Например, gcd (42, 56) = 14, следовательно,

${\ displaystyle {\ frac {42} {56}} = {\ frac {3 \ cdot 14} {4 \ cdot 14}} = {\ frac {3} {4}}.}$

Наименьшее общее кратное [ править ]

Наибольший общий делитель можно использовать для нахождения наименьшего общего кратного двух чисел, когда известен наибольший общий делитель, используя соотношение ^[1]

${\ displaystyle \ operatorname {lcm} (a, b) = {\ frac {| a \ cdot b |} {\ operatorname {gcd} (a, b)}}.}$

Расчет [ править ]

Использование разложения на простые множители [ править ]

Наибольшие общие делители могут быть вычислены путем определения разложения двух чисел на простые множители и сравнения множителей. Например, чтобы вычислить gcd (48, 180), мы находим факторизации на простые множители 48 = 2 ⁴  · 3 ¹ и 180 = 2 ²  · 3 ²  · 5 ¹ ; НОД тогда будет 2 ^{мин (4,2)}  · 3 ^{мин (1,2)}  · 5 ^{мин (0,1)} = 2 ²  · 3 ¹  · 5 ⁰ = 12, как показано на диаграмме Венна . Соответствующий НОК равен 2 ^{max (4,2)}  · 3 ^{max (1,2)}  · 5 ^{max (0,1)} = 2 ⁴ · 3 ²  · 5 ¹ = 720.

^[17]

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

Алгоритм Евклида [ править ]

Метод, введенный Евклидом для вычисления наибольших общих делителей, основан на том факте, что для двух положительных целых чисел a и b таких, что a > b , общие делители a и b совпадают с общими делителями a - b и b .

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

Например, чтобы вычислить gcd (48,18) , нужно действовать следующим образом:

${\displaystyle {\begin{aligned}(48,18)\quad &\to \quad (48-18,18)=(30,18)&&\to \quad (30-18,18)=(12,18)\\&\to \quad (12,18-12)=(12,6)&&\to \quad (12-6,6)=(6,6).\end{aligned}}}$

Итак, gcd (48, 18) = 6 .

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

Евклидов алгоритм [ править ]

Более эффективным методом является алгоритм Евклида , вариант, в котором разность двух чисел a и b заменяется остатком от евклидова деления (также называемого делением с остатком ) числа a на b .

Обозначив этот остаток в виде мод б , алгоритм заменяет ( , б ) по ( б , моды б ) несколько раз , пока пара не является ( г , 0) , где d представляет наибольший общий делитель.

Например, чтобы вычислить gcd (48,18), вычисление выглядит следующим образом:

${\displaystyle {\begin{aligned}(48,18)\quad &\to \quad (18,48{\bmod {1}}8)=(18,12)\\&\to \quad (12,18{\bmod {1}}2)=(12,6)\\&\to \quad (6,12{\bmod {6}})=(6,0).\end{aligned}}}$

Это снова дает gcd (48, 18) = 6 .

Алгоритм НОД Лемера [ править ]

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

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

Бинарный алгоритм GCD [ править ]

В двоичном алгоритме НОД используются только вычитание и деление на 2. Метод заключается в следующем: пусть a и b - два неотрицательных целых числа. Пусть целое число d равно 0. Есть пять возможностей:

• а = б .

Поскольку gcd ( a , a ) = a , желаемый GCD равен a × 2 ^d (поскольку a и b изменяются в других случаях, а d записывает, сколько раз a и b были разделены на 2 в следующем шаге, НОД исходной пары является произведением a и 2 ^d ).

• И a, и b четные.

Тогда 2 - общий делитель. Разделите a и b на 2, увеличьте d на 1, чтобы записать, сколько раз 2 является общим делителем, и продолжайте.

• a четное, а b нечетное.

Тогда 2 не является общим делителем. Разделите a на 2 и продолжайте.

• a нечетное, а b четное.

Тогда 2 не является общим делителем. Разделите b на 2 и продолжайте.

• И a, и b нечетные.

Поскольку gcd ( a , b ) = gcd ( b , a ), если a < b, то поменяйте местами a и b . Число c = a - b положительно и меньше a . Любое число, которое делит a и b, должно также делить c, поэтому каждый общий делитель a и b также является общим делителем b и c . Аналогично a = b + cи каждый общий делитель b и c также является общим делителем a и b . Таким образом, две пары ( a , b ) и ( b , c ) имеют одинаковые общие делители, и, следовательно, gcd ( a , b ) = gcd ( b , c ). Более того, поскольку a и b оба нечетны, c четно, процесс может быть продолжен с заменой пары ( a , b ) меньшими числами ( c / 2, b ) без изменения GCD.

Каждый из вышеперечисленных шагов уменьшает по крайней мере одно из a и b , оставляя их неотрицательными, и поэтому их можно повторять только конечное число раз. Таким образом, в конечном итоге процесс приводит к a = b , случаю остановки. Тогда НОД - это a × 2 ^d .

Пример: ( a , b , d ) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1); исходный НОД, таким образом, является произведением 6 из 2 ^d = 2 ¹ и a = b = 3.

Бинарный алгоритм GCD особенно легко реализовать на бинарных компьютерах. Его вычислительная сложность составляет

${\displaystyle O((\log a+\log b)^{2})}$

Вычислительная сложность обычно выражается длиной n входных данных. Здесь эта длина и сложность, таким образом,${\displaystyle n=\log a+\log b,}$

${\displaystyle O(n^{2})}$.

Другие методы [ править ]

${\displaystyle \gcd(1,x)=y,}$или функция Тома. Штриховка внизу указывает на эллипсы (т. Е. Отсутствие точек из-за очень высокой плотности).

Если a и b оба отличны от нуля, наибольший общий делитель a и b может быть вычислен с использованием наименьшего общего кратного (НОК) a и  b :

${\displaystyle \gcd(a,b)={\frac {|a\cdot b|}{\operatorname {lcm} (a,b)}}}$,

но чаще НОК вычисляется из НОД.

Используя функцию Тома f ,

${\displaystyle \gcd(a,b)=af\left({\frac {b}{a}}\right),}$

который обобщается на рациональные числа a и b или соизмеримые действительные числа.

Кейт Славин показал, что для нечетного a  ≥ 1:

${\displaystyle \gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})}$

которая является функцией, которая может быть вычислена для комплексного b . ^[18] Вольфганг Шрамм показал, что

${\displaystyle \gcd(a,b)=\sum \limits _{k=1}^{a}\exp(2\pi ikb/a)\cdot \sum \limits _{d\left|a\right.}{\frac {c_{d}(k)}{d}}}$

- целая функция от переменной b для всех натуральных чисел a, где c _d ( k ) - сумма Рамануджана . ^[19]

Сложность [ править ]

Вычислительная сложность из расчета наибольших общих делителей была широко изучена. ^[20] Если использовать алгоритм Евклида и элементарные алгоритмы умножения и деление, вычисление наибольшего общего делителя двух целых чисел в большинстве п бит являются Это означает , что вычисление наибольшего общего делителя имеет, с точностью до множителя постоянная , такая же сложность, как и умножение.${\displaystyle O(n^{2}).}$

Однако, если используется алгоритм быстрого умножения , можно модифицировать алгоритм Евклида для улучшения сложности, но вычисление наибольшего общего делителя становится медленнее, чем умножение. Точнее, если умножение двух целых чисел по n бит занимает время T ( n ) , то самый быстрый известный алгоритм для наибольшего общего делителя имеет сложность. Это означает, что самый быстрый из известных алгоритмов имеет сложность${\displaystyle O\left(T(n)\log n\right).}$${\displaystyle O\left(n\,(\log n)^{2}\right).}$

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

Таким образом, вычисление наибольших общих делителей относится к классу задач, решаемых за квазилинейное время . Тем более соответствующая задача решения принадлежит классу P задач, разрешимых за полиномиальное время. Неизвестно, что проблема GCD связана с NC , поэтому не существует известного способа ее эффективного распараллеливания ; также неизвестно , что он является P-полным , что означало бы, что вряд ли возможно эффективное распараллеливание вычислений GCD. Shallcross et al. показал, что родственная проблема (EUGCD, определение остаточной последовательности, возникающей во время алгоритма Евклида) NC-эквивалентна проблемецелочисленное линейное программирование с двумя переменными; если одна из проблем находится в NC или является P-полной , другая тоже. ^[21] Поскольку NC содержит NL , также неизвестно, существует ли компактный алгоритм для вычисления GCD, даже для недетерминированных машин Тьюринга.

Несмотря на то, что проблема не связана с ЧПУ , существуют параллельные алгоритмы, асимптотически более быстрые, чем алгоритм Евклида; Самый быстрый из известных детерминированных алгоритмов разработан Чором и Голдрайхом, который (в модели CRCW-PRAM ) может решить проблему за время O ( n / log n ) с помощью n ^{1 + ε} процессоров. ^[22] Рандомизированные алгоритмы могут решить проблему за O ((log n ) ² ) времени на процессорах ^{[ требуется пояснение ]} (это суперполином ).${\displaystyle \exp \left(O\left({\sqrt {n\log n}}\right)\right)}$^[23]

Свойства [ править ]

• Каждый общий делитель a и b является делителем gcd ( a , b ) .
• gcd ( a , b ) , где a и b не равны нулю, может быть определен альтернативно и эквивалентно как наименьшее положительное целое число d, которое может быть записано в форме d = a ⋅ p + b ⋅ q , где p и q - целые числа. Это выражение называется личностью Безу . Такие числа p и q можно вычислить с помощью расширенного алгоритма Евклида .
• gcd ( a , 0) = | а | , при a ≠ 0 , поскольку любое число является делителем 0, а наибольший делитель числа a равен | а |, ^{[3] [6]} Это обычно используется как базовый случай в алгоритме Евклида.
• Если a делит произведение b ⋅ c и gcd ( a , b ) = d , то a / d делит c .
• Если m - неотрицательное целое число, то gcd ( m ⋅ a , m ⋅ b ) = m ⋅gcd ( a , b ) .
• Если m - любое целое число, то gcd ( a + m ⋅ b , b ) = gcd ( a , b ) .
• Если m является положительным общим делителем a и b , то gcd ( a / m , b / m ) = gcd ( a , b ) / m .
• НОД является мультипликативной функцией в следующем смысле: если a ₁ и a ₂ взаимно просты, то gcd ( a ₁ ⋅ a ₂ , b ) = gcd ( a ₁ , b ) ⋅gcd ( a ₂ , b ) . В частности, вспоминая, что GCD является положительной целочисленной функцией, получаем, что gcd ( a , b ⋅ c ) = 1 тогда и только тогда, когда gcd ( a , b ) = 1 и gcd (а , в ) = 1 .
• НОД - это коммутативная функция: gcd ( a , b ) = gcd ( b , a ) .
• НОД является ассоциативной функцией: gcd ( a , gcd ( b , c )) = gcd (gcd ( a , b ), c ) . Таким образом, gcd ( a , b , c , ...) может использоваться для обозначения GCD нескольких аргументов.
• gcd ( a , b ) тесно связан с наименьшим общим кратным lcm ( a , b ) : мы имеем

  gcd ( a , b ) ⋅lcm ( a , b ) = | a ⋅ b | .

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

• Верны следующие версии дистрибутивности :

  gcd ( a , lcm ( b , c )) = lcm (gcd ( a , b ), gcd ( a , c ))

  lcm ( a , gcd ( b , c )) = gcd (lcm ( a , b ), lcm ( a , c )) .

• Если у нас есть уникальные разложения на простые множители a = p ₁ ^{e ₁} p ₂ ^{e ₂} ⋅⋅⋅ p _m ^{e _m} и b = p ₁ ^{f ₁} p ₂ ^{f ₂} ⋅⋅⋅ p _m ^{f _m,} где e _i ≥ 0 и f _i ≥ 0 , то НОД элементов a и b равен

  gcd ( a , b ) = p ₁ ^{min ( e ₁ , f ₁ )} p ₂ ^{min ( e ₂ , f ₂ )} ⋅⋅⋅ p _m ^{min ( e _m , f _m )} .

• Иногда полезно определить gcd (0, 0) = 0 и lcm (0, 0) = 0, потому что тогда натуральные числа становятся полной распределительной решеткой с GCD в качестве операции встречи и LCM в качестве операции соединения. ^[24] Это расширение определения также совместимо с обобщением для коммутативных колец, приведенным ниже.
• В системе декартовых координат , НОД ( , б ) можно интерпретировать как число сегментов между точками с целыми координатами на прямой отрезок прямой , соединяющей точки (0, 0) и ( , б ) .
• Для неотрицательных целых чисел a и b , где a и b не равны нулю, можно доказать, рассматривая алгоритм Евклида в базе  n : ^[25]

  НОД ( n ^a - 1, n ^b - 1) = n ^{gcd ( a , b )} - 1 .

• Тождество с участием totient функции Эйлера :

  ${\displaystyle \gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).}$

Вероятности и ожидаемое значение [ править ]

В 1972 году Джеймс Э. Ниманн показал, что k целых чисел, выбранных независимо и равномерно из {1, ...,  n }, взаимно просты с вероятностью 1 / ζ ( k ), когда n стремится к бесконечности, где ζ относится к дзета Римана. функция . ^[26] (Для вывода см. Взаимно простое число.) Этот результат был расширен в 1987 году, чтобы показать, что вероятность того, что k случайных целых чисел имеют наибольший общий делитель d, равна d ^−k / ζ ( k ). ^[27]

Используя эту информацию, можно увидеть (неформально) , что ожидаемое значение функции наибольшего общего делителя не существует, когда k  = 2. В этом случае вероятность того, что НОД равняется d, равна d ⁻² / ζ (2), и поскольку ζ (2) = π ² /6 имеем

${\displaystyle \mathrm {E} (\mathrm {2} )=\sum _{d=1}^{\infty }d{\frac {6}{\pi ^{2}d^{2}}}={\frac {6}{\pi ^{2}}}\sum _{d=1}^{\infty }{\frac {1}{d}}.}$

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

${\displaystyle \mathrm {E} (k)=\sum _{d=1}^{\infty }d^{1-k}\zeta (k)^{-1}={\frac {\zeta (k-1)}{\zeta (k)}}.}$

Для k  = 3 это примерно равно 1,3684. Для k  = 4 это примерно 1,1 · 106.

Если один аргумент GCD зафиксирован на некотором значении , он станет мультипликативной функцией в другой переменной, и можно показать, что ^{[ необходима ссылка ]}${\displaystyle m}$

${\displaystyle {\frac {1}{N}}\lim _{N\to \infty }\sum _{n=1}^{N}\gcd(n,m)=\prod _{p^{\alpha }||n}\left(1+\alpha -{\frac {\alpha }{p}}\right)}$

Здесь выполняется произведение по всем основным степеням , так что, кроме${\displaystyle \prod _{p^{\alpha }||n}}$${\displaystyle p^{\alpha }}$${\displaystyle p^{\alpha }|n}$${\displaystyle p^{\alpha +1}\not |n}$

В коммутативных кольцах [ править ]

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

Если R является коммутативным кольцом, а и б находятся в R , то элемент д из R называется общим делителем из и б , если она делит оба A и B (то есть, если есть элементы х и у в R такие, что d · x  =  a и d · y  =  b ). Если d является общим делителем a и bИ каждый общий делитель через и Ь делит d , то d называется наибольший общий делитель из и б .

При таком определении два элемента a и b вполне могут иметь несколько наибольших общих делителей или вообще не иметь. Если R является областью целостности, то любые два НОД для a и b должны быть ассоциированными элементами , поскольку по определению один из них должен делить другой; действительно, если НОД существует, любой из его партнеров также является НОД. Существование НОД не гарантируется в произвольных областях целостности. Однако, если R является уникальной областью факторизации , то любые два элемента имеют НОД, и в более общем плане это верно для доменов НОД . Если R - евклидова областьв котором евклидово деление задается алгоритмически (как, например, когда R = F [ X ], где F - поле , или когда R - кольцо целых гауссовских чисел ), тогда наибольшие общие делители могут быть вычислены с использованием формы Алгоритм Евклида, основанный на процедуре деления.

Ниже приведен пример целостной области с двумя элементами, не имеющими НОД:

${\displaystyle R=\mathbb {Z} \left[{\sqrt {-3}}\,\,\right],\quad a=4=2\cdot 2=\left(1+{\sqrt {-3}}\,\,\right)\left(1-{\sqrt {-3}}\,\,\right),\quad b=\left(1+{\sqrt {-3}}\,\,\right)\cdot 2.}$

Элементы 2 и 1 +  √ −3 являются двумя максимальными общими делителями (то есть, любой общий делитель, кратный 2, связан с 2, то же самое верно для 1 +  √ −3 , но они не связаны, поэтому не является наибольшим общим делителем a и  b .

В соответствии со свойством Безу мы можем в любом коммутативном кольце рассматривать набор элементов вида pa  +  qb , где p и q пробегают кольцо. Это идеал, порожденный a и b , и обозначается просто ( a ,  b ). В кольце, все идеалы которого являются главными (область главных идеалов или PID), этот идеал будет идентичен множеству кратных некоторого элемента кольца d ; тогда это d является наибольшим общим делителем a и b . Но идеал ( а,  b ) могут быть полезны даже тогда, когда нет наибольшего общего делителя a и b . (Действительно, Эрнст Куммер использовал этот идеал как замену НОД в своей трактовке Великой теоремы Ферма , хотя он представлял его как множество кратных некоторого гипотетического или идеального элемента кольца d , откуда и возник термин теоретико-кольцевой.)

См. Также [ править ]

• Безу домен
• Наименьший общий знаменатель
• Унитарный делитель

Заметки [ править ]

Ссылки [ править ]

• Эндрюс, Джордж Э. (1994) [1971], Теория чисел , Дувр, ISBN 9780486682525
• Харди, GH ; Райт, EM (1979), Введение в теорию чисел (пятое изд.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Лонг, Кальвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Lexington: DC Heath and Company , LCCN  77171950
• Петтофреццо, Энтони Дж .; Биркит, Дональд Р. (1970), Элементы теории чисел , Englewood Cliffs: Prentice Hall , LCCN  71081766

Дальнейшее чтение [ править ]

• Дональд Кнут . Искусство программирования , Том 2: получисловые алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89684-2 . Раздел 4.5.2: Наибольший общий делитель, стр. 333–356. 
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 31.2: Наибольший общий делитель, стр. 856–862. 
• Сондерс Маклейн и Гарретт Биркофф . Обзор современной алгебры , четвертое издание. MacMillan Publishing Co., 1977 г. ISBN 0-02-310070-2 . 1–7: «Евклидов алгоритм».