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

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

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

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

Обзор

Определение

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

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

Приведенное выше определение непригодно для определения gcd(0, 0) , поскольку не существует наибольшего целого числа n такого, что 0 × n = 0 . Однако ноль является своим собственным наибольшим делителем, если наибольшее значение понимается в контексте отношения делимости, поэтому gcd(0, 0) обычно определяется как 0 . Это сохраняет обычные тождества для НОД и, в частности, тождество Безу , а именно, что НОД( a , b ) порождает тот же идеал , что и { a , b } . Этому соглашению следуют многие системы компьютерной алгебры . Тем не менее, некоторые авторы оставляют gcd(0, 0) неопределённым.

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

Пример

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

$54\times 1=27\times 2=18\times 3=9\times 6.$

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

$1,2,3,6.$

Из них наибольшее число равно 6, поэтому оно является наибольшим общим делителем :

$\gcd(54,24)=6.$

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

Взаимнопростые числа

Основная статья: Взаимнопростые целые числа

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

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

Прямоугольник 24 на 60 покрыт десятью квадратными плитками размером 12 на 12, где 12 — это НОД, равный 24 и 60. В более общем смысле, прямоугольник a - b со стороной c можно покрыть квадратными плитками только . если c — общий делитель a и b .

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

Приложения

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

Дополнительная информация: Несократимая дробь.

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

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

Наименьшее общее кратное

Дополнительная информация: Наименьшее общее кратное.

Наименьшее общее кратное двух целых чисел, оба из которых не равны нулю, можно вычислить по их наибольшему общему делителю, используя соотношение

$\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 ^{макс(4,2)}  · 3 ^{макс(1,2)}  · 5 ^{макс(0,1)} = 2 ⁴  · 3 ²  · 5 ¹ = 720.

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

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

Основная статья: алгоритм Евклида

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

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

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

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

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

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

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

Основная статья: алгоритм Евклида

Анимация, показывающая применение алгоритма Евклида для поиска наибольшего общего делителя 62 и 36, то есть 2.

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

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

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

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

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

Бинарный алгоритм НОД

Основная статья: Бинарный алгоритм НОД

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

Алгоритм двоичного НОД существенно отличается от алгоритма Евклида тем, что каждое четное число, встречающееся во время вычислений, делится на два. Его эффективность обусловлена ​​тем, что в двоичном представлении проверка четности состоит из проверки самой правой цифры, а деление на два состоит из удаления самой правой цифры.

Метод заключается в следующем, начиная с a и b , которые являются двумя положительными целыми числами, НОД которых ищется.

1. Если a и b оба четные, разделите оба на два, пока хотя бы одно из них не станет нечетным; пусть d будет числом этих парных делений.
2. Если а четное, то делим его на два, пока оно не станет нечетным.
3. Если b четное, то делим его на два, пока оно не станет нечетным.

   Теперь a и b нечетны и останутся нечетными до конца вычислений.

4. Пока а ≠ b делай
   • Если a > b , то замените a на a – b и разделите результат на два, пока a не станет нечетным (поскольку a и b оба нечетны, существует как минимум одно деление на 2).
   • Если a < b , то замените b на b – a и разделите результат на два, пока b не станет нечетным.
5. Теперь a = b и наибольший общий делитель равен $2^{d}a.$

Шаг 1 определяет d как высшую степень двойки , которая делит a и b и, следовательно, их наибольший общий делитель. Ни один из шагов не меняет набор нечетных общих делителей a и b . Это показывает, что когда алгоритм останавливается, результат правильный. Алгоритм в конце концов останавливается, поскольку каждый шаг делит хотя бы один из операндов как минимум на 2 . При этом количество делений на 2 и, следовательно, количество вычитаний не превышает общего количества цифр.

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

Алгоритм двоичного НОД особенно прост в реализации и особенно эффективен на двоичных компьютерах. Его вычислительная сложность составляет

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

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

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

$O(n^{2})$.

Алгоритм НОД Лемера

Основная статья: алгоритм НОД Лемера

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

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

Другие методы

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

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

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

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

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

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

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

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

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

это функция, которую можно вычислить для комплексного b . Вольфганг Шрамм показал, что

$\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 ) — сумма Рамануджана .

Сложность

Вычислительная сложность вычисления наибольших общих делителей широко изучена. Если использовать алгоритм Евклида и элементарные алгоритмы умножения и деления, вычисление наибольшего общего делителя двух целых чисел длиной не более n бит равно O ( n ² ) . Это означает, что вычисление наибольшего общего делителя с точностью до постоянного множителя имеет ту же сложность, что и умножение.

Однако если используется быстрый алгоритм умножения , можно изменить алгоритм Евклида для повышения сложности, но вычисление наибольшего общего делителя становится медленнее, чем умножение. Точнее, если умножение двух целых чисел из n бит занимает время T ( n ) , то самый быстрый известный алгоритм нахождения наибольшего общего делителя имеет сложность O ( T ( n ) log n ) . Это означает, что самый быстрый известный алгоритм имеет сложность O ( n (log n ) ² ) .

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

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

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

Свойства

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

  НОД( а , б )⋅lcm( а , б ) знак равно | а ⋅ б | .

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

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

  НОД( a , lcm( b , c )) = lcm(НОД( a , b ), НОД( a , c ))

  lcm( a , НОД( b , c )) = НОД(lcm( a , b ), lcm( a , c )) .

• Если у нас есть уникальные простые факторизации a = p ₁ ^{и ₁} п ₂ ^e_е2 ⋅⋅⋅ п _м ^e_в и б = р ₁ ^{ж ₁} п ₂ ^f_f2 ⋅⋅⋅ п _м ^{ж _м} где e _i ≥ 0 и fi _≥ 0 , то НОД a и b равен

  НОД( а , б ) знак равно п ₁ ^{мин( е ₁ , ж ₁ )} п ₂ ^{мин( е ₂ , ж ₂ )} ⋅⋅⋅ п _м ^{мин( е _м , ж _м )} .

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

  НОД( н ^а − 1, н ^б − 1) = п ^{НОД( а , б )} − 1 .

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

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

• $\sum _{k=1}^{n}\gcd(k,n)=n\sum _{d|n}{\frac {\varphi (d)}{d}}=n\prod _{p|n}\left(1+\nu _{p}(n)\left(1-{\frac {1}{p}}\right)\right)$ где $\nu _{p}(n)$ — p -адическая оценка.

и

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

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

$\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 , ожидаемое значение четко определено, и согласно приведенному выше аргументу оно равно

$\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,1106.

В коммутативных кольцах

См. Также: Делитель (теория колец)

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

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

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

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

$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 . Но идеал ( a , b ) может быть полезен даже тогда, когда не существует наибольшего общего делителя a и b . (Действительно, Эрнст Куммер использовал этот идеал в качестве замены НОД в своей трактовке Великой теоремы Ферма , хотя он представлял его как набор кратных некоторого гипотетического или идеального кольцевого элемента d , откуда и возник теоретико-кольцевой термин.)

См. также

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

Ссылки

• Эндрюс, Джордж Э. (1994) [1971], Теория чисел , Дувр, ISBN  978-0-486-68252-5
• Харди, штат Джорджия ; Райт, Э.М. (1979), Введение в теорию чисел (пятое изд.), Оксфорд: Oxford University Press , ISBN  978-0-19-853171-5
• Лонг, Кэлвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: DC Heath and Company , LCCN   77171950
• Петтофреззо, Энтони Дж.; Биркит, Дональд Р. (1970), Элементы теории чисел , Энглвуд Клиффс: Прентис Холл , 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.
• Сондерс Мак Лейн и Гаррет Биркгоф . Обзор современной алгебры , четвертое издание. Издательство Макмиллан, 1977. ISBN   0-02-310070-2 . 1–7: «Алгоритм Евклида».