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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
«Дві вертикальні лінії поділені рисочками на відрізки однакової довжини. На кожному кроці, довжина коротшого сегменту виділяється а потім видаляється з довшого сегменту. На останньому кроці, обидва сегменти однакові, і обидва видаляються.»
Анімація алгоритму Евкліда для чисел 252 та 105. Рисочки відповідають числам кратним 21, найбільшому спільному дільникові (НСД). На кожному кроці менше число віднімають від більшого, поки одне з них не дорівнюватиме нулю. Число, що лишилось і є НСД.

Алгоритм Евкліда (також називається евклідів алгоритм) — ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, котрий описав його в книгах VII та X Начал.[1]

Найбільший спільний дільник двох чисел це найбільше число, що ділить обидва дані числа без залишку. Алгоритм Евкліда оснований на тому, що НСД не змінюється, якщо від більшого числа відняти менше. Наприклад, 21 є НСД чисел 252 та 105 (252 = 21 × 12; 105 = 21 × 5); оскільки 252 − 105 = 147, НСД 147 та 105 також 21. Оскільки більше з двох чисел постійно зменшується, повторне виконання цього кроку дає все менші числа, поки одне з них не дорівнюватиме нулю. Коли одне з чисел дорівнюватиме нулю, те, що залишилось, і є НСД. Обертаючи кроки алгоритму Евкліда у зворотний порядок, НСД можна виразити як лінійну комбінацію даних чисел помножених на цілі коефіцієнти, наприклад 21 = 5 × 105 + (−2) × 252. Ця важлива властивість відома як лема Безо.

Найдавніший опис алгоритму знаходиться в Началах Евкліда (біля 300 до н. е.), що робить його найдавнішим чисельним алгоритмом, яким користуються і нині. Оригінальний варіант алгоритму описував роботу лише з натуральними числами та геометричними довжинами (дійсними числами), алгоритм було узагальнено в XIX столітті на роботу з іншими типами чисел, такими як Гаусові цілі та поліноми з однією змінною. Це призвело до появи сучасних алгебраїчних понять, таких як Евклідові класи. Алгоритм Евкліда було узагальнено ще далі для роботи з іншими математичними структурами, такими як вузли та поліноми від багатьох змінних.

Алгоритм евкліда має багато застосувань на практиці, та в теорії. З його допомогою можна згенерувати практично всі найважливіші музичні ритми різних культур у всьому світі.[2] Алгоритм Евкліда відіграє ключову роль в алгоритмі RSA, поширеному методі криптографії з відкритим ключем. Його також використовують для пошуку розв'язків Діофантових рівнянь, наприклад, пошук чисел, що задовільняють декільком умовам (Китайська теорема про залишки) або зворотні числа в скінченному полі. Алгоритм Евкліда також застосовують для побудови ланцюгових дробів в методі Штурма для пошуку дійсних коренів полінома, та в сучасних методах факторизації цілих. Нарешті, він виступає простим інструментом для доведення теорем в теорії чисел, таких, як теорема Лагранжа про чотири квадрата та основної теореми арифметики.

Алгоритм Евкліда ефективно обчислює НСД великих чисел, оскільки виконує операцій не більше, ніж вп'ятеро більше кількості цифр меншого числа (в десятковій системі). Цю властивість було доведено Ґабріелєм Ламі (англ. Gabriel Lamé) в 1844 році, що позначило початок теорії складності обчислень. Методи підвищення ефективності алгоритму були розроблені в XX столітті.

Вступ[ред.ред. код]

Найбільший спільний дільник[ред.ред. код]

Алгоритм Евкліда обчислює найбільший спільний дільник (НСД) двох натуральних чисел a та b. Найбільший спільний дільник g — це найбільше натуральне число яке ділить як a так і b без залишку. Найбільший спільний дільник також записують як НСД(ab) або, простіше, (ab)[3] хоча останнє позначення використовують і для інших математичних понять, таких як координати дво-вимірних векторів.

Якщо НСД(ab) = 1, тоді a та b називають взаємно простими.[4] Ця властивість не залежить від того, чи прості числа a та b.[5] Наприклад, ні 6 ні 35 не прості, оскільки їх можна розкласти на добутки 6 = 2 × 3 та 35 = 5 × 7. Однак, 6 та 35 взаємно прості. Жодне натуральне число окрім 1 не ділить водночас 6 та 35, оскільки у них нема спільних дільників.

«Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall.»
Прямокутник з ребрами 24 одиниці на 60 покрито квадратами з ребром 12 одиниць, де 12 це НСД 24 та 60. В загальному випадку, прямокутник з ребрами a на b може бути покрито квадратами з ребром c тоді і лише тоді, коли c є НСД a та b.

Нехай g = НСД(ab). Оскільки a та b є добутками g, їх можна записати, як a = mg та b = ng, і не існує більшого числа G > g з такою ж властивістю. Натуральні числа m та n мають бути взаємно простими, оскільки інший спільний дільник може бути виділений з m та n, що збільшить g. Таким чином, будь-яке число c, що ділить a та b має ділити і g. Найбільший спільний дільник g чисел a та b може бути визначений, як спільний дільник, який можна поділити іншим спільним дільником c.[6]

Поняття НСД можна проілюструвати наступним чином.[7] Розглянемо прямокутник зі сторонами a та b, та будь-який спільний дільник c, що ділить і a, і b без залишку. Ребра прямокутника можна поділити на відрізки довжиною c, які поділять прямокутник на сітку квадратів зі стороною c. Найбільший спільний дільник g дорівнює найбільшому можливому значенню c. Наприклад, прямокутник 24 на 60 може бути покрита сіткою квадратів зі стороною 1, 2, 3, 6 або 12. Таким чином, 12 є найбільшим спільним дільником 24 та 60. Прямокутник 24 на 60 можна поділити сіткою квадратами з ребром 12, два квадрати вздовж одного ребра (24/12 = 2), та п'ятеро (60/12 = 5) вздовж іншого.

Найбільший спільний дільник a та b можна визначити як добуток спільних дільників обох чисел.[8] Наприклад, оскільки 462 можна розкласти на добуток 2 × 3 × 7 × 11 а 1071 можна розкласти на добуток 3 × 3 × 7 × 17, найбільший спільний дільник 462 та 1071 дорівнює 21 = 3 × 7, добутку їхніх спільних дільників. Якщо два числа не мають спільних дільників, їх найбільший спільних дільник 1 і вони взаємно прості. Ключовою перевагою алгоритма Евкліда є ефективне знаходження НСД без необхідності обчислення дільників.[9][10] Розклад великих цілих чисел на дільники є криптографічно складною задачею, яка лежить в основі багатьох сучасних криптографічних систем.[11]

НСД трьох або більшої кількості чисел дорівнює добутку дільників спільних для трьох чисел,[12] який можна обчислити на основі НСД пар чисел.[13] Наприклад,

НСД(abc) = НСД(a, НСД(bc)) = НСД(НСД(ab), c) = НСД(НСД(ac), b).

Тобто, алгоритм Евкліда обчислення найбільшого спільного дільника двох цілих підходить і для обчислення НСД довільної кількості цілих.

Характеристики[ред.ред. код]

Алгоритм[ред.ред. код]

{a} = {q_0} {b} + {r_0} \qquad \text{(0)}

{b} = {q_1} {r_0} + {r_1} \qquad \text{(1)}

{r_0} = {q_2} {r_1} + {r_2} \qquad \text{(2)}

{r_1} = {q_3} {r_2} + {r_3} \qquad \text{(3)}

\dots

{r_{n-3}} = {q_{n-1}} {r_{n-2}} + {r_{n-1}} \qquad \text{(n-1)}

{r_{n-2}} = {q_n} {r_{n-1}} + 0 \qquad \text{(n)}

Алгоритм Евкліда ітеративний, тобто, пошук розв'язку відбувається за декілька кроків. Для того щоб знайти НСД(a, b) на 0-му кроці знаходять остачу r0 від ділення a на b. На 1-му кроці знаходять остачу від ділення b на r0. Оскільки залишки зменшуються на кожному кроці але не можуть бути від'ємними, то цю операцію виконують n кроків до тих пір поки не отримують остачу 0. Найбільшим спільним дільником є остання не нульова остача rn−1. Кількість кроків в алгоритмі має бути скінченною, оскільки існує лише скінченна кількість цілих чисел між початковим залишком r0 та нулем.

Доведення Алгоритму Евкліда[ред.ред. код]

Правильність алгоритму Евкліда можна довести за два кроки.[14] Спочатку необхідно довести, що rn−1 дійсно є дільником a та b, а потім необхідно довести, що це є найбільший спільний дільник.

Доведення, що {r_{n-1}} є дільником a та b[ред.ред. код]

З n-го кроку випливає, що ~{r_{n-2}} \;\vdots\; {r_{n-1}} ({r_{n-2}} ділиться на {r_{n-1}}). Підставимо ~{r_{n-2}} в n-1-ий крок. Маємо:

~{r_{n-3}} = {q_{n-1}} {q_n} {r_{n-1}} + {r_{n-1}}

~{r_{n-3}} = {r_{n-1}} ({q_{n-1}} {q_n}  + 1)

Таким чином ~{r_{n-3}} \;\vdots\; {r_{n-1}}. Повторимо цю операцію n разів і отримаємо, що ~{a} \;\vdots\; {r_{n-1}} та ~{b} \;\vdots\; {r_{n-1}}. Отже, ~{r_{n-1}} є дільником a та b.

Доведення, що {r_{n-1}} є найбільшим дільником a та b[ред.ред. код]

За означенням число ~{d} називається найбільшим спільним дільником a та b, тоді і тільки тоді, коли для будь-якого числа ~ \forall {k} для якого виконується: ~ {a} \;\vdots\; {k} та ~{b} \;\vdots\; {k} має виконуватись, що ~{d} \;\vdots\; {k}.

Нехай k є дільником a та b, тоді ~{a} \;\vdots\; {k} та ~{b} \;\vdots\; {k} або можна сказати, що існують такі числа ~{a_1} та ~{b_1}, що

~{a} = {a_1} {k}

~{b} = {b_1} {k}

Підставимо в 1-ий крок алгоритму:

~{a_1} {k} = {q_0} {b_1} {k} + {r_0} і виконаємо перетворення:

~{r_0} = {a_1} {k} - {q_0} {b_1} {k}

~{r_0} = {k} ({a_1} - {q_0} {b_1})

Отже, ~{r_0} \;\vdots\; {k}. Підставимо ~{r_0} в 2-ий крок і аналогічно продовжимо до тих пір поки з останнього кроку не отримаємо, що ~{r_{n-1}} \;\vdots\; {k}, що доводить те, що ~{r_{n-1}} є найбільшим спільним дільником.

Реалізації[ред.ред. код]

Реалізації алгоритму можна записати у псевдокоді. Наприклад, версію, основану на операції ділення, можна запрограмувати наступним чином:[15]

функція нсд(a, b)
    поки b ≠ 0
       t := b
       b := a mod b
       a := t
    поверни a

На початку k-ої ітерації, змінна b має значення останнього залишку rk−1, а змінна a має значення поперднього залишку rk−2. Крок b := a mod b еквівалентний рекурсивній формулі rkrk−2 mod rk−1. Допоміжна змінна t має значення rk−1 поки відбувається обчислення наступного залишку rk. В кінці циклу, змінна b має значення залишку rk, а змінна a має значення поперднього rk−1.

В описаній Евклідом версії алгоритму, обчислення залишку (b = a mod b) замінено повторним відніманням.[16]

функція нсд(a, b)
    якщо a = 0
       поверни b
    поки b ≠ 0
        якщо a > b
           a := a − b
        інакше
           b := b − a
    поверни a

Змінні a та b поперемінно мають значення попередніх залишків rk−1 та rk−2. Якщо a більше за b на початку ітерації; тоді a дорівнює rk−2, оскільки rk−2 > rk−1. Протягом циклу, a зменшується на число, кратне попередньому залишку b доки a не стане менше за b. Тоді a стає наступним залишком rk. Потім b зменшується на число, кратне a поки не стане менше за a, даючи значення наступного залишку rk+1, і так далі.

Рекурсивна версія [17] основана на рівності НСД послідовних залишків та умові зупинки НСД(rN−1, 0) = rN−1.

функція нсд(a, b)
    якщо b = 0
       поверни a
    інакше
       поверни нсд(b, a mod b)

Наприклад, НСД(1071, 462) обчислюють на основі еквівалентного значення НСД(462, 1071 mod 462) = НСД(462, 147). Яке, в свою чергу, обчислюють на основі НСД(147, 462 mod 147) = НСД(147, 21), а це, обчислють від НСД(21, 147 mod 21) = НСД(21, 0) = 21.

Метод найменших абсолютних залишків[ред.ред. код]

В іншому варіанті реалізації алгоритму Евкліда на кожному кроці частку збільшують на 1 якщо отримане абсолютне значення від'ємного залишку менше за додатній залишок.[18][19] В інших версіях, в рівнянні

rk−2 = qk rk−1 + rk

припускалось, що rk−1 > rk > 0. Однак, інший від'ємний залишок ek можна обчислити наступним чином:

rk−2 = (qk + 1) rk−1 + ek

де rk−1 вважається додатнім. Якщо |ek| < |rk|, тоді rk замінюють на ek. Як показано Леопольдом Кронекером, цей варіант витрачає найменшу кількість кроків у порівнянні з іншими варіантами алгоритму.[18][19]

Історія[ред.ред. код]

Ймовірно, алгоритм Евкліда було відкрито за століття до народження Евкліда, показаного на картині з циркулем.

Алгоритм Евкліда один з найдавніших алгоритмів, що досі використовують.[20] Він описаний в Началах Евкліда (приблизно 300 до н. е.), а саме, в книгах VII та X. В сьомій книзі алгоритм описано для цілих чисел, а в десятій — для довжин відрізків. Можна сказати, що алгоритм описано для дійсних чисел. Однак, довжина, площа та об'єм, що їх вимірюють нині в дійсних числах, вимірюють у різних одиницях та не існує універсальної природньої одиниці для вимірювання довжини, площі або об'єму. Також поняття дійсних цисел в ті часи було ще не відоме. Другий алгоритм геометричний. НСД двох довжин a та b відповідає довжині найдовшого відрізку g, яким можна виміряти a та b без залишку; іншими словами, довжини відрізків a та b дорівнюють добуткові довжини g на ціле число.

Можливо, алгоритм було відкрито не Евклідом, а він лише використав результати, отримані попередниками в Началах.[21][22] Математик та історик Ван дер Варден вважає, що книгу VII написано на основі підручника з теорії чисел авторства одного з математиків школи Піфагора.[23] Ймовірно, алгоритм був відомий ще Евдоксу Кіндському (приблизно 375 до н. е.).[24][25] Можливо, навіть, алгоритм був відомий ще до Евдокса,[26][27] судячи з використання поняття грец. ἀνθυφαίρεσις (антифарезис) в роботах Евкліда та Арістотеля.[28]

Нові можливості застосування алгоритму Евкліда було знайдено в XIX столітті. В 1829 році Чарльз Штурм застосував алгоритм Евкліда в методі Штурма для пошуку дійсних коренів поліномів у заданому інтервалі.[29]

Алгоритмічна ефективність[ред.ред. код]

«Множина кольорових ліній що виходять з початку декартової системи координат. Кожна лінія відповідає множині пар чисел, для обчислення НСД яких необхідна однакова кількість кроків за алгоритмом Евкліда.»
Кількість кроків необхідних для обчислення НСД(x, y) за алгоритмом Евкліда. Червоним позначено точки, які вимагають порівняно небагато кроків (швидке обчислення), жовтими, зеленими та синіми позначено більшу кількість кроків у зростаючому порядку (повільне обчислення).

Обчислювальну ефективність алгоритму Евкліда ретельно досліджено.[30] Ефективність роботи можна описати як необхідну алгоритму кількість кроків помножену на обчислювальні витрати кожного кроку. Як було показано Ґабріелєм Ламі в 1844 році,[31] кількість необхідних кроків ніколи не більша за кількість цифр hдесятковій системі) меншого з чисел b помножена на 5.[32][33] Оскільки обчислювальні витрати кожного кроку зазвичай порядку h, загальні витрати зростають на рівні h2.

Кількість кроків[ред.ред. код]

Кількість кроків необхідних для обчислення НСД пари натуральних чисел, a та b, можна позначити як T(ab).[34] Якщо g є НСД a та b, тоді a = mg та b = ng де m та n взаємно прості числа. Тоді

T(a, b) = T(m, n)

що можна отримати поділивши всі кроки алгоритму на g.[35] Аналогічно, кількість кроків лишається незмінною якщо a та b помножити на спільний дільник w: T(a, b) = T(wa, wb). Таким чином, кількість кроків T може сильно відрізнятись для пари сусідніх чисел, наприклад T(a, b) та T(ab + 1), в залежності від розміру обох НСД.

Рекурсивна природа алгоритму Евкліда дає наступне рівняння

T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1

де T(x, 0) = 0 за припущенням.[36]

Кількість кроків у найгіршому випадку[ред.ред. код]

Якщо алгоритму Евкліда необхідні N кроків для обчислення НСД натуральних чисел a > b > 0, то найменші числа, для яких це дійсне, є числа Фібоначчі FN+2 та FN+1.[37] Цю властивість можна довести методом математичної індукції.[38] Якщо N = 1, b ділить a без залишку; найменші натуральні числа, для яких це вірне — b = 1 та a = 2, які дорівнюють F2 та F3 відповідно. Припустімо, що це вірно для значень N не більших за M − 1. Першим кроком M-крокового алгоритму є a = q0b + r0, а другим b = q1r0 + r1. Оскільки алгоритм рекурсивний, йому необхідно M − 1 кроків для знаходження НСД(br0) та найменшими значеннями є FM+1 та FM. Таким чином, a має найменше значення коли q0 = 1, що значить a = b + r0 = FM+1 + FM = FM+2. Це доведення, оприлюднене Ґабріелем Ламі в 1844 заклало основи теорії обчислювальної складності,[39] а також є першим застосуванням чисел Фібоначчі на практиці.[40]

Цього результату достатньо, аби показати, що алгоритм Евкліда виконує кроків не більше, ніж вп'ятеро більше кількості цифр меншого числа (в десятковій системі).[41] Якщо алгоритму потрібно більше N кроків, тоді b більше або дорівнює FN+1, що, в свою чергу. більше або дорівнює φN−1, де φ дорівнює золотому перетину. Оскільки b ≥ φN−1, тоді N − 1 ≤ logφb. Оскільки log10φ > 1/5, (N − 1)/5 < log10φ logφb = log10b. Таким чином, N ≤ 5 log10b. Звідси випливає, що алгоритм Евкліда потребує менше за O(h) ділень, де h дорівнює кількості цифр в меншому числі b.

Середня кількість кроків[ред.ред. код]

Середню кількість кроків необіхдних алгоритму Евкліда було визначено в три різні способи. Перше визначення, це середній час T(a) необхідний для обчислення НСД заданого числа a та меншого натурального числа b обраного з рівною ймовірністю з цілих від 0 до a - 1[42]


T(a) = \frac{1}{a} \sum_{0 \leq b<a} T(a, b).

Однак, оскільки T(ab) істотно змінюється в залежності від НСД обох чисел, усереднена функція T(a) також містить «шум».[43]

Аби зменшити цей шум, використовують друге середнє τ(a) для взаємно простих до a чисел.


\tau(a) = \frac{1}{\varphi(a)} \sum_{0 \leq b<a, \mathrm{GCD}(a, b) = 1} T(a, b).

Всього існує φ(a) взаємно простих чисел менших за a, де φ це функція Ейлера. Значення τ поступово зростає разом з a[44][45]

τ(a) = (12/π2) ln 2 ln a + C + O(a−(1/6) + ε)

з похибкою порядку a−(1/6) + ε, де ε нескінченно мала. Стала C в цій формулі дорівнює

C = −(1/2) + 6 (ln 2/π2)( 4γ − 24π2ζ '(2) + 3 ln 2 − 2) ≈ 1.467

де γ це Стала Ейлера — Маскероні, а ζ' — похідна дзета-функції Рімана.[46][47] Значення основного коефіцієнту (12/π2) ln 2 було визначено двома незалежними методами.[48][49]

Оскільки перше середнє може бути обчислене на основі тау середнього додаванням дильників d числа a[50]


T(a) = \frac{1}{a} \sum_{d | a} \varphi(d) \tau(d)

воно може бути наближене формулою[51]

T(a) ≈ C + (12/π2) ln 2 ( ln a − Σd|a Λ(d)/d )

де Λ(d) — функція фон Мангольда.[52]

Третє середнє Y(n) визначають як середню кількість кроків необхідних для обчислення НСД коли a та b випадкові числа (рівномірно розподілені) від 1 до n[51]


Y(n) = \frac{1}{n^{2}} \sum_{a=1}^{n} \sum_{b=1}^{n} T(a, b) = \frac{1}{n} \sum_{a=1}^{n} T(a).

Заміна наближеною формулою для T(a) в це рівняння дає оцінку Y(n)[53]

Y(n) ≈ (12/π2) ln 2 ln n + 0.06.

Обчислювальні витрати за крок[ред.ред. код]

На кожному кроці k алгоритму Евкліда, обчислюють частку qk та залишок rk для пари цілих rk−2 та rk−1

rk−2 = qk rk−1 + rk.

Основні витрати за крок полягають в обчисленні qk, оскільки залишок rk можна швидко обчислити на основі rk−2, rk−1 та qk

rk = rk−2qk rk−1.

Обчислювальна складність ділення h-бітних чисел змінюються як O(h(+1)), де  — довжина частки.[54]

Для порівняння, оригінальний варіант алгоритму на основі віднімання може бути набагато повільнішим. Ділення цілого еквівалентне q віднімань, де q — частка. Якщо відношення a до b велике, частка буде також великою і знадобиться велика кількість віднімань. З іншого боку, було показано, що частки найімовірніше матимуть невиликі значення. Ймовірність отримати частку q приблизно ln|u/(u − 1)| де u = (q + 1)2.[55] Наприклад, ймовірність отримати частку 1, 2, 3, або 4 дорівнює приблизно 41.5%, 17.0%, 9.3%, та 5.9%, відповідно. Оскільки операція віднімання швидша за ділення, особливо для великих чисел,[56] оснований на відніманні алгоритм Евкліда може бути на рівні з основаним на діленні.[57] Цю властивість використано в бінарному алгоритмі Евкліда.[58]

Поєднання оцінки кількості кроків з оцінкою обчисльювальних витрат на крок показує, що витрати алгоритму Евкліда зростають квадратично (h2) в залежності від середньої кількості цифр h в заданих числах. Нехай h0, h1, …, hN−1 дорівнює кількості цифр в послідовних залишках r0r1, …, rN−1. Оскільки кількість кроків N зростає пропорційно h, час роботи алгоритму обмежено


O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2)\Big)\subseteq O(h(h_0+2N))\subseteq O(h^2).

Приклад[ред.ред. код]

Обчислимо НСД чисел 1071 та 1029.

a b Пояснення
НСД( 1071, 1029) Початкові аргументи
= НСД( 1029, 42) 1071 mod 1029 = 42
= НСД( 42, 21) 1029 mod 42 = 21
= НСД( 21, 0) 42 mod 21 = 0
= 21 Оскільки b=0, то повертаємо a=21

У випадку невеликих чисел, можна використати послідовне ділення у стовпчик. Наприклад, нам потрібно знайти НСД (2700, 1520):

Nsd.jpg


Отже, НСД (2700, 1520) = 20.

Дивись також[ред.ред. код]

Посилання[ред.ред. код]

  1. Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
  2. Godfried Toussaint, "The Euclidean algorithm generates traditional musical rhythms, " Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47—56.
  3. Stark, ст. 16.
  4. Stark, ст. 21.
  5. LeVeque, ст. 32.
  6. Leveque, p. 31.
  7. Grossman JW (1990). Discrete Mathematics. New York: Macmillan. с. 213. ISBN 0-02-348331-8. 
  8. Schroeder, ст. 21-22.
  9. Schroeder, ст. 19.
  10. Ogilvy CS, Anderson JT (1966). Excursions in number theory. New York: Oxford University Press. с. 27–29. LCCN 66-14484. 
  11. Schroeder, ст. 216—219.
  12. Stark, p. 25.
  13. Ore, pp. 47-48.
  14. Stark, ст. 16-20.
  15. Knuth, ст. 319—320.
  16. Knuth, ст. 318—319.
  17. Stillwell, ст. 14.
  18. а б Ore, p. 43.
  19. а б Stewart BM (1964). Theory of Numbers (вид. 2nd). New York: Macmillan. с. 43–44. LCCN 64-10964. 
  20. Knuth, p. 318.
  21. Weil A (1983). Number Theory. Boston: Birkhäuser. с. 4–6. ISBN 0-8176-3141-0. 
  22. Jones A (1994). «Greek mathematics to AD 300». Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. с. 46–48. ISBN 0-415-09238-8. 
  23. van der Waerden BL (1954). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. с. 114–115. 
  24. Knuth, p. 318.
  25. von Fritz K The Discovery of Incommensurability by Hippasus of Metapontum // Ann. Math.. — 46 (1945) С. 242–264. DOI:10.2307/1969021.
  26. Heath TL (1949). Mathematics in Aristotle. Oxford Press. с. 80–83. 
  27. Fowler DH (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. с. 31–66. ISBN 0-19-853912-6. 
  28. Becker O Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid 2 (1933) С. 311–333.
  29. Sturm C Mémoire sur la résolution des équations numériques // Bull. des sciences de Férussac. — 11 (1829) С. 419–422.
  30. Knuth, pp. 339–364.
  31. Lamé G Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers // Comptes Rendus Acad. Sci.. — 19 (1844) С. 867–870.
  32. Grossman H On the Number of Divisions in Finding a G.C.D. // The American Mathematical Monthly. — 31 (1924). DOI:10.2307/2298146.
  33. Honsberger R (1976). Mathematical Gems II. The Mathematical Association of America. с. 54–57. ISBN 0-88385-302-7. 
  34. Knuth, p. 344.
  35. Ore, p. 45.
  36. Knuth, p. 344.
  37. Knuth, p. 343.
  38. Mollin, p. 21.
  39. LeVeque, p. 35.
  40. Knuth, p. 343.
  41. Mollin, pp. 21–22.
  42. Knuth, p. 344.
  43. Knuth, p. 353.
  44. Knuth, p. 357.
  45. Tonkov T On the average length of finite continued fractions // Acta arithmetica. — 26 (1974) С. 47–57.
  46. Porter JW On a Theorem of Heilbronn // Mathematika. — 22 (1975) С. 20–28.
  47. Knuth DE Evaluation of Porter's Constant // Computers and Mathematics with Applications. — 2 (1976) С. 137–139. DOI:10.1016/0898-1221(76)90025-0.
  48. Dixon JD The Number of Steps in the Euclidean Algorithm // J. Number Theory. — 2 (1970) С. 414–422. DOI:10.1016/0022-314X(70)90044-2.
  49. Heilbronn HA (1969). «On the Average Length of a Class of Finite Continued Fractions». У Paul Turán. Number Theory and Analysis. New York: Plenum. с. 87–96. LCCN 68-8991. 
  50. Knuth, p. 354.
  51. а б Norton GH On the Asymptotic Analysis of the Euclidean Algorithm // Journal of Symbolic Computation. — 10 (1990) С. 53–58. DOI:10.1016/S0747-7171(08)80036-3.
  52. Knuth, p. 355.
  53. Knuth, p. 356.
  54. Knuth, pp. 257–261.
  55. Knuth, p. 352.
  56. Wagon S (1999). Mathematica in Action. New York: Springer-Verlag. с. 335–336. ISBN 0-387-98252-3. 
  57. Cohen, p. 14.
  58. Cohen, pp. 14–15, 17–18.