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

Анимација на Евклидовиот алгоритам за броевите 252 и 105. Единичните сегменти се всушност со должина 21, што е најголемиот заеднички делител (НЗД) на дадените броеви. Во секој чекор, помалиот број се одзема од поголемиот, додека еден од нив не се сведе на нула. Останатите се појдовни броеви на НЗД.

Евклидов алгоритам — ефикасен начин во математиката, за одредување на најголемиот заеднички делител (НЗД) на дадените броеви. Алгоритмот е именуван по старогрчкиот математичар Евклид, кој го спомнал во својата книга Елементи.

НЗД на два броја е најголемиот број што истовремено ги дели и двата броја без остаток. Евклидовиот алгоритам се заснова на начелото дека најголемиот заеднички делител на два броја не се менува ако помалиот број се одземе од поголемиот број, а потоа се определи НЗД на новодобиениот број и помалиот од претходните два. На пример, 21 е НЗД за 252 и 105 (252 = 21 × 12; 105 = 21 × 5); бидејќи е 252 - 105 = 147, НЗД за 147 и 105 е исто така 21. Бидејќи на овој начин се намалува поголемиот од двата почетни броја, со повторување на постапката ќе се добијат сè помали и помали броеви, додека еден од нив не се сведе на нула. Во тој момент, вториот број е еднаков на најголемиот заеднички делител на двата почетни броја. Ако редоследот на чекорите во Евклидовиот алгоритам е обратен, НЗД може да се изрази како збир од два почетни броја, од кои секој се множи со цел број, во претходниот пример е 21 = 5 × 105 + (−2) × 252. Оваа важна особина е позната како Безуов идентитет.

Првиот познат опис на Евклидовиот алгоритам е пронајден во Елементите (околу 300 г.пр.н.е.), што го прави најстариот нумерички алгоритам кој сè уште е во активна употреба. Во оригиналот било објаснето само за природни броеви и геометриски должини (реални броеви), но во 19 век бил обопштен на полиноми со една променлива и на Гаусови цели броеви, што довело до развој на нови концепти за апстрактната алгебра како што е Евклидовиот домен. Евклидовиот алгоритам е дополнително обопштен за други математички структури, како што се јазлите и повеќепроменливите полиноми.

Евклидовиот алгоритам има широка теоретска и практична примена. Претставува клучен елемент на РСА алгоритам, метод на асиметрична криптографија што е широко користен во електронското деловно работење. Се користи при решавање на диофантски равенки, на пример при определување на броеви кои задоволуваат повеќекратни конгруенции (Кинеска теорема на остатоци) или при определување на мултипликативната инверзна на конечно поле. Може да се користи за конструирање на верижни дропки, во Штурмовиот метод за одредување на реалните нули на полиномите и неколку други современи алгоритми за факторизација на природни броеви. Конечно, Евклидовиот алгоритам е основната алатка за докажување на теоремите на модерната теорија на броеви, како што е Лагранжовата теорема за четири квадрати и основната теорема на аритметиката за уникатната факторизација на природните броеви.

Евклидовиот алгоритам е ефикасен начин да се одреди НЗД на големи броеви бидејќи не му требаат повеќе чекори од петкратниот број на цифри на помалиот број запишан со основа 10, што го докажал Габриел Ламе во 1844 година и со тоа го означил почетокот на теоријата на комплексност. Во 20 век , биле развиени методи за подобрување на ефикасноста на Евклидовиот алгоритам.

Историја

Евклидовиот алгоритам веројатно бил познат со векови пред раѓањето на Евклид. Дел од фреската на Рафаеловата Атинска школа на која е прикажан Евклид со неговите ученици.

Евклидовиот алгоритам е еден од најстарите алгоритми кои сè уште се користат. Во писмена форма, првпат се појавува во Евклидовите Елементи во 3 век пр.н.е., и тоа во книгите VII (тврдења 1 и 2) и X (тврдењата 2 и 3). Во книгата, алгоритмот е формулиран за цели броеви, додека во книгата е дадена примената на подолги броеви, па тој е со геометриска природа. НЗД за дадени должини a и b одговара должината g која e најдолгата можна должина со која може да се измерат подеднакво должините a и b. Со други зборови, должините a и b може да се добијат со множење со должината g со некој цел број.

Многу е веројатно дека Евклид не е изворниот творец на алгоритмот, бидејќи претходно познатото математичко знаење го собрал во „Елементите“. Математичарот и историчар Ван дер Варден верува дека седмата книга Елементи е заснована на учебник за теорија на броеви, напишан од математичари од Питагоровата школа. Постојат индиции дека самиот алгоритам бил познат уште во Евдокс од Книд (околу 375 г.пр.н.е.), и можно е да е постар, судејќи според неговата употреба технички термин, реципрочно одземање во делата на Евклид и Аристотел.

Со векови подоцна, Евклидовиот алгоритам бил повторно откриен независно во Индија и Кина, првенствено како средство за одредување решенија за диофантските равенки кои се појавиле при решавање на астрономски проблеми и правење точни календари. Во втората половина на петтиот век, индискиот математичар и астроном Ариабхата го опишал алгоритамот како „дробилка“, можеби поради неговата ефикасност во решавањето на диофантските равенки. Иако како посебен случај кинеската теорема за остатоци веќе била наведена од кинескиот математичар и астроном Сун-цу во 5 век од нашата ера, општото решение во 1247 година го објавил Чин Чу-шао во неговото дело Цзју чжан суан шу (кинески: 數書九章, Девет книги за математичката вештина).

Во Европа, Евклидовиот алгоритам за првпат бил опишан од Баше во второто издание на неговото дело (Пријатни проблеми за уживање, 1624), и се претпоставува дека се користел при решавањето на диофантските равенки и при конструкцијата на верижни дропки. Проширениот Евклидов алгоритам, како метод за ефикасно пресметување на верижните дропки, го објавил англискиот математичар Николас Сандерсон, припишувајќи му го на Роџер Коутс.

Во 19 век, благодарение на Евклидовиот алгоритам, биле развиени нови системи на броеви, како што се Гаусовите и Ејзенштајновите цели броеви. Гаус во 1815 година го користел Евклидовиот алгоритам за да ја прикаже единствената факторизација на неговите цели броеви, иако тоа дело било објавено речиси две децении подоцна, во 1832 година, а самиот алгоритам првпат бил спомнат во неговата книга Аритметички истражувања (латински: Disquisitiones Arithmeticae) објавена во 1801 година, но само како метод за работа со верижни дропки.

Се чини дека Дирихле бил првиот автор кој го сметал Евклидовиот алгоритам како еден од основните елементи на теоријата на броеви. Тој забележал дека многу од резултатите од теоријата на броеви (на пример, единствена факторизација) би биле вистинити во кој било друг броен систем каде што може да се примени Евклидовиот алгоритам. Предавањата на Дирихле за теоријата на броеви биле дополнети и ревидирани од Рихард Дедекинд, кој го користел Евклидовиот алгоритам за проучување на нов општ вид на броеви - алгебарски цели броеви. Тој бил првиот што ја докажал теоремата на Ферма за збир на два квадрати користејќи ја единствената факторизација на Гаусови цели броеви. Дополнително, Дедекинд го дефинирал и концептот на Евклидовиот домен, броен систем во кој е можно да се дефинира обопшувањето на Евклидовиот алгоритам. На крајот на 19 век, Евклидовиот алгоритам бил постепено занемарен во корист на поопштата теорија за идеалите на Дедекинд.

„Евклидовиот алгоритам е покривката на сите алгоритми, бидејќи е најстариот преживеан нетривијален алгоритам. "

Доналд Кнут, (1981). стр. 318.

Процесот на наоѓање апликации на Евклидовиот алгоритам, кој започнал во 19 век, продолжил до ден-денес. Шарл Штурм во 1829 година покажал дека алгоритмот може да се користи во Штурмовата верига, што се користи за броење на реалните нули на полином во произволно избран интервал.

Евклидовиот алгоритам бил првиот алгоритам за определување на целобројна поврзаност, односно за пронаоѓање цели броеви меѓу споредливи реални броеви. На крајот на 20 век, биле развиени неколку нови алгоритми кои можат да ја проверуваат целобројната поврзаност, на пример Фергусон-Форкејдовиот алгоритам и и нему сродни, алгоритам LLL , алгоритам HJLS и алгоритам PSLQ

Во 1969 година стратешка игра за двајца играчи заснована на Евклидовиот алгоритам се појавила под името Евклидова игра. На почетокот, пред играчите има два купчиња со a, односно b камчиња. Тие наизменично земаат камчиња од поголемиот куп, што е некој производ од бројот на камчиња во помалиот куп. Конкретно, ако во одреден момент има x, односно y кмачиња, каде x е поголемо од y, играчот на потез може да го намали поголемото купче од x на x − ky камчиња, под услов бројот на камчиња што ги отстранува да биде ненегативен цел број. Победникот е првиот играч кој ќе успее да ги отстрани сите камчиња од едно купче.

Алгоритам

Начело

Евклидовиот алгоритам има итеративна природа, што значи дека конечниот резултат се добива во низа чекори, додека меѓурезалтатот од произволен чекор се користи во првиот следен чекор. Ако k e цел број што се користи за означување на чекорите на алгоритмот почнувајќи од нула е еднаков, тогаш на првиот чекор му одговара  k= 0, на вториот k = 1, и така натаму.

Секој чекор започнува со два ненегативни остатоци r_k−1 и r_k−2. Бидејќи алгоритмот осигурува дека со секој чекор остатоците постојано се намалуваат, тој е помал од неговиот претходник. Целта на k-тиот чекор е да се определи количникот и остатокот на таков начин што важи еднаквоста:

r_k−2 = q_k r_k−1 + r_k

при што r_k < r_k−1. Со други зборови, множителите на помалиот број r_k−1 се одземаат од поголемиот број r_k−2 сè додека добиениот остаток е помал од r_k−1.

Во првиот чекор ( = 0), остатоците ₋₂ и ₋₁ се еднакви и соодветно, и тоа се токму броевите за кои се бара НЗД. Во следниот чекор ( = 1), остатоците стануваат еднакви на остатокот од почетниот чекор... Врз основа на ова, алгоритмот може да биде претставен со низа еднаквости:

a = q₀ b + r₀

b = q₁ r₀ + r₁

r₀ = q₂ r₁ + r₂

r₁ = q₃ r₂ + r₃

…

Ако a е помала од b, во првиот чекор од алгоритмот, броевите треба да се заменат, односно за a  < ''b, почетниот количник q₀ е еднаков на нула, а остатокот r₀ е еднаков на a. Така, r_k е помал од неговиот претходник r_k−1 за сите k ≥ 0.

Бидејќи остатоците се намалуваат во секој чекор, и затоа што не можат да бидат негативни, преостанатиот r_N мора да стане еднаков на нула во одреден момент, и тогаш алгоритмот запира. Последниот остаток r_N−1 што се разликува од нула е најголемиот заеднички делител за броевите a и b. Бројот N не може да биде бесконечен бидејќи помеѓу нула и првиот остаток r₀ постои конечен број на ненегативни цели броеви.

Доказ на валидноста

Валидноста на Евклидовиот алгоритам може да се докаже во два чекори. Во првиот чекор, се покажува дека последниот r_N−1 е различен од нула и истовремено ги дели a и b. Бидејќи е заеднички делител, мора да биде помал или еднаков на најголемиот заеднички делител g. Во вториот чекор, се покажува дека произволен заеднички делител на броевите a и b, вклучувајќи го и g, мора да го дели r_N−1; оттука следи дека g мора да биде помал или еднаков на r_N−1. Двата добиени заклучоци се конзистентни само во случај кога r_N−1 = g.

За да се покаже првиот чекор, односно дека r_N−1 ги дели истовремено и a и b, најпрво треба да се забележи дека r_N−1 го дели својот претходник r_N−2

r_N−2 = q_N r_N−1

бидејќи последниот остаток r_N е еднаков на нула. r_N−1 го дели и r_N−3

r_N−3 = q_N−1 r_N−2 + r_N−1

затоа истовремено ги дели двата собироци од десната страна на еднаквоста. Разгледувајќи ги редум останатите претходници, се добива дека и r_N−1 ги дели сите, вклучувајќи ги a и b. Од друга страна ниеден од преостанатите остатоци r_N−2, r_N−3, итн. не ги дели истовремено a и b бидејќи во еднаквостите се секогаш се јавува остаток. Со оглед дека r_N−1 е заеднички делител на броевите a и b, мора r_N−1≤g.

Во вториот чекор треба да се добие произволен природен број c кој истовремено ги дели a и b (произволен заеднички делител на броевите a и b) кој мора да го дели и остатокот r_k. По дефиниција, a и b може да бидат запишани како множеници на бројот c: a = mc и b = nc, при што m и n се природни броеви. Оттука следи дека c го дели првиот остаток r₀, бидејќи важи следната низа еднаквости:

r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c.

Аналогно може да се добие дека c ги дели остатоците r₁, r₂, итн. Заклучок е дека НЗД g мора да го дели r_N−1, откаде следува g ≤ r_N−1. Бидејќи според првиот чекор r_N−1 ≤ g, мора g = r_N−1. Затоа g е најголемиот заеднички делител на сите следни парови:

g = НЗД(a, b) = НЗД(b, r₀) = НЗД(r₀, r₁) = … = НЗД(r_N−2, r_N−1) = r_N−1

Пример за користење на алгоритмот

Анимација на алгоритмот во кој почетниот правоаголник е целосно покриен со сè помали квадрати. Димензиите на зелениот правоаголник се = 1071 и = 462. Го покриваат портокаловите квадрати на страница 462 што е можно подолго, по што останува зелен правоаголник со димензии 462×147. Потоа е покриен со сини квадрати со должина на страна 147, а зелениот правоаголник со димензии 21×147 останува како вишок. Може да биде целосно покриен со црвени квадрати чија должина на страна е 21. Тоа значи дека 21 е НЗД броевите 1071 и 462.

Како илустрација, со Евклидов алгоритам може да се одреди најголемиот заеднички делител на броевите a = 1071 и b = 462. Прво од бројот 1071 се одзема бројот 462 сè додека не се добие остаток кој е помал од 462. Таа постапка може да се повтори двапати (q₀ = 2), со остаток 147:

1071 = 2 × 462 + 147.

Потоа постапката се повторува за броевите 462 и 147 додека новиот остаток не стане помал од 147, што ќе се случи по третото одземање (₁ = 3), а добиениот остаток ќе биде 21:

462 = 3 × 147 + 21.

Во третиот чекор, 21 се одзема од 147 додека новиот остаток не биде помал од 21. Постапката може да се повтори седум пати ( ₂ = 7) без остаток.

147 = 7 × 21 + 0.

Бидејќи последниот остаток е нула, алгоритмот завршува, при што 21 е најголемиот заеднички делител на броевите 1071 и 462. Добиениот резултат се совпаѓа со НЗД (1071, 462) определен со факторизација на прости броеви. Опишаната постапка може да се прикаже и во табела:

Чекор	Еднаквост	Количник и остаток
0	1071 = q0 × 462 + r0	q0 = 2 и r0 = 147
1	462 = q1 × 147 + r1	q1 = 3 и r1 = 21
2	147 = q2 × 21 + r2	q2 = 7 и r2 = 0; алгоритмот завршува

Визуелизација

Евклидовиот алгоритам може да се прикаже и визуелно користејќи ја аналогијата на прекривање на правоаголници со квадрати. Претпоставката е дека е потребно целосно да се покрие правоаголникот со димензии „пати“ со квадрати, со подолгата страна. Прво, се обидува да ја покрие страницата со квадрати; оваа постапка дава непокриен правоаголен вишок од димензии „ ₀ пати“, каде што ₀ <. Потоа, користејќи го квадратот на страница ₀, покријте го вишокот. Во овој процес се добива нов непокриен правоаголник со димензии „ ₁ на ₀ “. За да го покриете, користете ги квадратите од страница ₁ итн. Постапката завршува кога нема повеќе непокриен вишок, односно кога квадратите целосно ќе го покријат правоаголникот. Должината на страната на најмалиот квадрат е НЗД за броевите што ги сочинуваат страните на почетниот правоаголник. На пример, најмалиот квадрат на соседната слика е страница 21 (прикажано со црвено), а 21 е НЗД броевите 1071 и 462, кои се димензиите на почетниот правоаголник (прикажано со зелено).

Одредување на количник и остаток

На секој чекор k, Евклидовиот алгоритам го пресметува количникот q_k и остатокот r _k користејќи два дадени броја r_k−1 и r< sub> 'k−2

r_k−2 = q_k r _k−1 + r_k

при што r_k по апсолутна вредност е строго помала од r_k−1. Алгоритмот за делење обезбедува дека таков количник и остаток секогаш постојат. Дополнително, алгоритам за деливост за природни броеви тврди дека q_k и r _k е единствен, но оваа состојба не е потребна за Евклидовиот алгоритам.

Во Евклидовата изворна верзија на алгоритмот, количникот и остатокот се одредуваат со повторено одземање: r_k−1 се одзема од r_k−2 до остатокот r_k станува помал од r_k−1. Поефикасен пристап користи целобројна поделба (т.н. операција div) за пресметување на количникот и одредување на остатокот при делење на цел број (т.н. операција mod) за пресметување на остатокот. Резултатот од операцијата mod е остатокот при делење два броја; поради тоа,

r_k ≡ r_k−2 мод r_k−1

Остатокот е еквивалентен на класата на конгруентност во модуларната аритметика.

Имплементации

Имплементацијата на алгоритам може да се претстави со псевдокод. На пример, верзијата заснована на споделување може да биде програмирана на следниов начин

function НЗД(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

На почетокот на k-тата итерација, во променливата b се наоѓа последниот остаток r_k−1, додека променливата a го содржи неговиот претходник, r_k−2. Редицата од кодот каде b := a е мод b одговара на рекурзивна формула r_k ≡ r_k−2 мод r_k−1. Помошна променлива t ја складира вредноста на r_k−1 во времето кога следниот остаток е пресметан r_k. Во последниот чекор од итеративната јамка, променливата b го складира остатокот од r_k, а променливата a на неговиот претходник, остатокот r_k−1.

Во Евклидовата верзија заснована на одземање, пресметувањето на остатокот (b = a мод b) се заменува со повторено одземање.

function НЗД(a, b)
    if a = 0
       return b
    while b ≠ 0
        if a > b
           a := a − b
        else
           b := b − a
    return a

Променливите a и b наизменично ги задржуваат претходните остатоци r_k−1 и r_k−2. Ако на почетокот на повторувањето a е поголемо од b, тогаш a ја добива вредноста r< sub>k−2, бидејќи r_k−2 > r_{k− 1}. За време на извршувањето на циклусот a се намалува со одземање на претходниот остаток од b додека a не стане помала од b. Тогаш a е следниот остаток од r_k. Тогаш b се намалува со одземање на a додека не стане помала од него, а потоа станува еднаква на r_{k +1}. Процесот продолжува додека b не стане еднаква на нула.

Рекурзивна верзија се заснова на еднаквоста на најголемиот заеднички делител на последователни остатоци и на резултатот од условот врз основа на кој се излегува од циклусот НЗД(r' 'N −1, 0) = rN−1.

function НЗД(a, b)
    if b = 0
       return a
    else
       return НЗД(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.

Метод на најмали апсолутни остатоци

Постои верзија на Евклидовиот алгоритам во која количникот се зголемува за еден на секој чекор ако добиениот негативен остаток е помал во апсолутната вредност од типичниот позитивен остаток.</ref> Во претходните случаи, еднаквоста

r_k−2 = q_k r_k−1 + r_k

претпоставува дека r_k−1 > r_k >   0. Сепак, можно е да се користи алтернативниот негативен остаток e_k:

r_k−2 = (q_k + 1) r_k−1 + e_k

каде што r_k−1 е, по претпоставка, позитивен број. Ако |e_k| < |r_k|, потоа r_k се заменува со e_k. Леополд Кронекер докажал дека овој метод ја одредува НЗД во најмал број чекори во споредба со сите други верзии на Евклидовиот алгоритам.

Други бројни системи

Како што веќе беше објаснето, Евклидовиот алгоритам се користи за одредување НЗД на два природни броја. Сепак, можно е да се направи обопштување на реални броеви и на егзотични бројни системи како што се полиноми, квадратни цели броеви и Хурвицови кватерниони, и да се користи тоа за прикажување на основното својство на единствената факторизација, т.е. фактот дека таквите броеви можат да се разложат на единствен начин на несводливи елементи кои се еквивалентни на прости броеви. Единствената факторизација е клучен услов за многу докази од теоријата на броеви.

Пример

НЗД на два полиноми $P(x)=x^{5}+x^{4}-x^{3}-3x^{2}-3x-1\,$ и $Q(x)=x^{4}-2x^{3}-x^{2}-2x+1\,$ го наоѓаме на следниов начин користејќи го Евклидовиот алгоритам (со скратување и проширување):

1. ${\frac {x^{5}+x^{4}-x^{3}-3x^{2}-3x-1}{x^{4}-2x^{3}-x^{2}-2x+1}}=x+3,R(1)=6x^{3}+2x^{2}+2x-4;({\frac {P(x)}{Q(x)}}=S(1)+R(1))$

1а. ${\frac {6x^{3}+2x^{2}+2x-4}{2}}=3x^{3}+x^{2}+x-2;({\frac {R(1)}{2}}=R(1s))$

2. ${\frac {3x^{4}-6x^{3}-3x^{2}-6x+3}{3x^{3}+x^{2}+x-2}}=x-{\frac {7}{3}},R(2)=-{\frac {5}{3}}x^{2}-{\frac {5}{3}}x-{\frac {5}{3}};({\frac {3Q(x)}{R(1s)}}=S(2)+R(2))$

2а. ${\frac {-{\frac {5}{3}}x^{2}-{\frac {5}{3}}x-{\frac {5}{3}}}{-{\frac {5}{3}}}}=x^{2}+x+1;({\frac {R(2)}{-{\frac {5}{3}}}}=R(2s))$

3. ${\frac {3x^{3}+x^{2}+x-2}{x^{2}+x+1}}=3x-2,R(3)=0;({\frac {R(1s)}{R(2s)}}=S(3))$

$NZD(P(x),Q(x))=R(2s)=x^{2}+x+1\,$

Примени во математиката

Безуов идентитет

Според Безуовиот идентитет, најголемиот заеднички делител, означен со g, на два цели броја a и b може да се прикаже како нивна линеарна комбинација. Ова значи дека секогаш е можно да се одредат цели броеви s и t да важи еднаквоста g = sa + tb.

Назначените броеви s и t може да се пресметаат со помош на количникот q₀, q₁, итн. со промена на редоследот во равенката во Евлидовиот алгоритам. Почнувајќи од претпоследната равенка g може да се изрази со помош на количникот q_N−1 и двата претходни остатоци, r_N−2 и r_N−3.

g = r_N−1 = r_N−3 − q_N−1 r_N−2

Наведените остатоци можат, аналогно, да бидат прикажани со помош на соодветните количници и остатоци.

r_N−2 = r_N−4 − q_N−2 r_N−3

r_N−3 = r_N−5 − q_N−3 r_N−4

Со замена на r_N−2 и r_N−3 со претходните еднаквости во првата равенка се добива g како линеарна сума на остатоците r_N−4 и r_N−5. Овој процес на изразување на остатоците со формули кои ги вклучуваат претходниците може да се продолжи додека не се достигнат појдовните броеви a и b:

r₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = a − q₀ b

Откако сите остатоци r₀, ..., r_N се заменети, добиената еднаквост го прикажува g како линеарна комбинација на броевите као линеарну комбинацију бројева a и b: g = sa + tb. Со самото тоа, Безуовиот идентитет, и претходната постапка можат да бидат обопштени во контекст на Евклидовите домени.

Верижни дропки

Евклидовиот алгоритам е тесно поврзан со верижните дропки. во облик:

a/b = q₀ + r₀/' 'b

b/r₀ = q₁ + r ₁/r₀

r₀/r₁ = q₂ + r₂/r₁

…

r_k−2/r_k−1 = - {q_k + r_k/r _k−1

…

r_N−2/r_N−1 = - {q_N

Последниот член од десната страна на секоја еднаквост е секогаш еднаков на реципрочната вредност на елементот од левата страна на следната еднаквост. Од првите две еднаквости се добива:

a/b = q₀ + 1/(q₁ > + r₁/r₀)

Ако, тогаш, користејќи го третото равенство, се замени дропката r₁/r₀, се добива:

a/b = q₀ + 1/(q₁ > + 1/(q₂ + r₂/r ₁))

На секој чекор, последното собирање во облик на дропка r_k/r_{k −1</ sub> секогаш може да се замени со користење на следното равенство во низата, кое завршува со последното. Резултатот е континуирана фракција}

a/b = q₀ + 1/(q₁ > + 1/(q₂ + 1/(… + 1/q_N))… ) = [q₀; q₁, q₂, ..., q _N]

Како што е веќе определено НЗД(1071, 462), а како што пресметаните количници q_k беа соодветно 2, 3 и 7, дропката 1071/ 462 е може да се запише

1071/462 = 2 + 1/(3 + 1/7) = [2; 3, 7]

што може да се потврди со пресметка.

Белешки

a. ^{^} Во некои широко прифатени учебници на англиски јазик, како што е Херштајн (англиски: Israel Nathan Herstein) Topics in Algebra, или Ланговиот (англиски: Serge Lang) Algebra, поимот „Евклидов алгоритам“ се користи за означување алгоритам за делење. Сепак, тоа е теорема, а не алгоритам.

b. ^{^} Во модерната употреба, би се рекло дека е формулирано за реални броеви. Но, бидејќи должините, плоштините и зафатнините, иако во денешно време се претставени со реални броеви, не се изразуваат во исти мерни единици, ниту пак постои природна единица за должина, површина и зафатнина, идејата за реални броеви тогаш не постоела. време.

 

Надворешни врски

• Интерактивна демонстрација на Евклидовиот алгоритам (англиски)
• Евклидов алгоритам (англиски)
• Евклидов алгоритам и игра базирана на него (англиски)
• [6] (англиски)