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

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

У математици, Еуклидов алгоритам[a] је ефикасан начин за одређивање највећег заједничког делиоца (НЗД) датих бројева. Алгоритам носи име по старогрчком математичару Еуклиду, који га је навео у VII и X књизи својих Елемената.[1]

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

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

Еуклидов алгоритам има широку теријску и практичну примену. Представља кључан елемент RSA алгоритма, методе асиметричне криптографије која се у значајној мери примењује у електронском пословању. Користи се при решавању диофантских једначина, на пример код одређивања бројева који задовољавају вишеструке конгруенције (Кинеска теорема о остацима) или при одређивању мултипликативног инверза коначног поља. Може се употребити за коструисање верижних разломака, у Штурмовој методи за одређивање реалних нула полинома, и још неколико савремених алгоритама за факторизацију природних бројева. На крају, Еуклидов алгоритам је основно средство за доказивање теорема модерне теорије бројева, као што су Лагранжова теорема о четири квадрата и основна теорема аритметике о јединственој факторизацији природних бројева.

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

Историја[уреди | уреди извор]

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

Еуклидов алгоритам је један од најстаријих алгоритама који се још увек употребљава.[2] У писаном облику, први пут се појављује у Еуклидовим Елементима у 3. веку п. н. е., и то у VII (тврђења 1[3] и 2[4]) и X књизи (тврђења 2[5] и 3[6]). У VII књизи, алгоритам је формулисан за целе бројеве, док је у X књизи дата примена на дужи, па је он геометријске природе.[b] НЗД за дате дужи a и b одговара дужи g која је највећа могућа дуж којом се могу измерити a и b подједнако. Другим речима, дужи a и b се могу добити множењем дужи g неким целим бројем.

Врло је вероватно да Еуклид није оригинални творац алгоритма, јер је он у Елементима сабрао до тада позната математичка знања.[7] Математичар и историчар ван дер Варден сматра да је седма књига Елемената заснована на уџбенику теорије бројева који су написали математичари из питагорејске школе.[8] Постоје индиције да је сам алгоритам био познат још Еудоксу са Книда (око 375. п. н. е.),[9][10] а могуће је и да је старији,[11][12] судећи по употреби техничког термина ἀνθυφαίρεσις (anthyphairesis, реципрочно одузимање) у делима Еуклида и Аристотела.[13]

Вековима касније, Еуклидов алгоритам је поново независно откривен у Индији и Кини,[14] првенствено као средство за одређивање решења диофантских једначина које су се појављивале при решавању астрономских проблема и прављењу прецизних календара. У другој половини петог века, индијски математичар и астроном Ариабхата описао је алгоритам као „дробилицу“,[15] можда због његове ефикасности у решавању диофантских једначина.[16] Иако је посебан случај Кинеске теореме о остацима навео већ кинески математичар и астроном Сун Тзу[17] у 5. веку нове ере, опште решење је 1247. године објавио Цин Цзу-шао у својом делу Цзју чжан суан шу (кин: 數書九章, Девет књига о математичкој вештини).[18]

У Европи, Еуклидов алгоритам је први пут описао Баше у другом издању свог дела Problèmes plaisants et délectables (Пријатни проблеми за уживање, 1624),[15] а претпоставља се да је коришћен у решавању диофантских једначина и при конструкцији верижних разломака. Проширени Еуклидов алгоритам је, као методу за ефикасно израчунавање верижних разломака, објавио енглески математичар Николас Саундерсон, приписавши га Роџеру Коутсу.[19]

У 19. веку, захваљујући Еуклидовом алгоритму, дошло је до развоја нових бројевних система, као што су Гаусови и Ејзенштајнови цели бројеви. Гаус је 1815. године употребио Еуклидов алгоритам да покаже јединствену факторизацију својих целих бројева, иако је тај рад објављен тек скоро две деценије касније, 1832. године[20], а сам алгоритам је први пут споменут у његовој књизи Аритметичка истраживања (лат. Disquisitiones Arithmeticae) објављеној 1801. године, али само као метода за рад са верижним разломцима.[14]

Чини се да је Дирихле био први аутор који је сматрао Еуклидов алгоритам за један од основних елемената теорије бројева.[21] Приметио је да би велики број резултата теорије бројева (на пример, јединствена факторизација), био тачан у било ком другом систему бројева у коме би се могао применити Еуклидов алгоритам.[22] Дирихлеова предавања о теорији бројева допунио је и прерадио Рихард Дедекинд, који је користио Еуклидов алгоритам за изучавање новог општег типа бројева - алгебарских целих бројева. Први је доказао Фермаову теорему о збиру два квадрата користећи јединствену факторизацију Гаусових целих бројева.[23] Поред тога, Дедекинд је дефинисао и концепт Еуклидовог домена, бројевног система у коме је могуће дефинисати уопштење Еуклидовог алгоритма. Крајем 19. века, Еуклидов алгоритам је постепено занемарен у корист Дедекиндове општије теорије идеала.[24]

„Еуклидов алгоритам је дека свих алгоритама, пошто је то најстарији нетривијални алгоритам који је преживео до данас.“

Доналд Кнут, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition. 1981. стр. 318..

Процес изналажења примена Еуклидовог алгоритма започет у 19. веку, наставио се до данас. Шарл Штурм је 1829. године показао да се алгоритам може употребити у Штурмовом ланцу који се користи за пребројавање реалних нула полинома у произвољно изабраном интервалу.[25]

Еуклидов алгоритам је био први алгоритам за утврђивање целобројне повезаности, односно за налажење целобројних односа између самерљивих реалних бројева. Крајем 20. века је развијено неколико нових алгоритама који могу да проверавају целобројну повезаност[26][27], на пример Фергусон-Форкејд алгоритам,[28] и њему сродни, ЛЛЛ алгоритам[29], HJLS алгоритам[30], и PSLQ алгоритам.[31]

Године 1969. под називом Еуклидова игра појавила се стратешка игра за два играча заснована на Еуклидовом алгоритму.[32] На почетку, испред играча се налазе две гомиле са a, односно b каменчића. Они наизменично узимају по m каменчића са веће гомиле, где је m неки умножак броја каменчића у мањој гомили. Конкретно, уколико се у неком тренутку на гомилама налази x, односно y каменчића, где је x веће од y, играч на потезу може смањити већу гомилу са x на xky каменчића, под условом да је број каменчића које одузима ненегативан цео број. Победник је први играч коме пође за руком да избаци све каменчиће из једне гомиле.[33][34]

Алгоритам[уреди | уреди извор]

Принцип[уреди | уреди извор]

Еуклидов алгоритам је итеративне природе, што значи да се крајњи резултат добија у низу корака, док се међурезултат произвољног корака користи у првом следећем.[35] Уколико је k цео број којим су означени кораци алгоритма почевши од нуле, првом кораку одговара једнакост k = 0, другом k = 1, и тако даље.

Сваки корак почиње са два ненегативна остатка rk−1 и rk−2. Како алгоритам осигурава да се остаци сваким кораком непрекидно смањују, rk−1 је мање од свог претходника rk−2. Циљ k-тог корака је да се одреде количник qk и остатак rk такви да важи једнакост

rk−2 = qk rk−1 + rk

где је rk < rk−1. Другим речима, умношци мањег броја rk−1 се одузимају од већег броја rk−2 све док је добијени остатак мањи од rk−1.

У првом кораку (k = 0), остаци r−2 иr−1 су једнаки a и b респективно, а то су управо бројеви за које се тражи НЗД. У следећем кораку (k = 1), остаци постају једнаки b и остаку почетног корака r0... На основу тога, алгоритам се може представити низом једнакости

a = q0 b + r0
b = q1 r0 + r1
r0 = q2 r1 + r2
r1 = q3 r2 + r3

Уколико је a мање од b, у првом кораку алгоритма треба заменити бројеве, односно, за a < b, почетни количник q0 је једнак нули, а остатак r0 је једнак a. На тај начин, rk је мањи од свог претходника rk−1 за све k ≥ 0.

Како се остаци смањују у сваком кораку, и како не могу бити негативни, остатак rN у неком тренутку мора постати једнак нули, па се тада алгоритам зауставља.[36] Последњи остатак rN−1 који је различит од нуле је највећи заједнички делилац бројева a и b. Број N не може бити бесконачан пошто између нуле и првог остатка r0 постоји коначан број ненегативних целих бројева.

Доказ валидности[уреди | уреди извор]

Валидност Еуклидовог алгоритма се може доказати у два корака.[37] У првом кораку показује се да последњи остатак rN−1 различит од нуле дели истовремено и a и b. Како је у питању заједнички делилац, он мора бити мањи или једнак највећем заједничком делиоцу g. У другом кораку се показује да произвољан заједнички делилац бројева a и b, укључујући и g, мора да дели и rN−1; одатле следи да g мора бити мање или једнако rN−1. Добијена два закључка су конзистентна само у случају да је rN−1 = g.

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

rN−2 = qN rN−1

пошто је последњи остатак rN једнак нули. rN−1 дели и rN−3

rN−3 = qN−1 rN−2 + rN−1

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

У другом кораку треба добити да произвољан природан број c који истовремено дели и a и b (произвољан заједнички делилац бројева a и b) мора да дели и остатак rk. По дефиницији, a и b могу бити записани као умношци броја c: a = mc и b = nc, при чему су m и n природни бројеви. Одатле следи да c дели први остатак r0, јер важи следећи низ једнакости:

r0 = a − q0b = mc − q0nc = (m − q0n)c.

Аналогно се може добити да c дели и остатке r1, r2, итд. Закључак је да НЗД g мора да дели rN−1, одакле је g ≤ rN−1. Како је према првом кораку rN−1 ≤ g, мора бити g = rN−1. Зато је g највећи заједнички делилац свих следећих парова:[38][39]

g = НЗД(a, b) = НЗД(b, r0) = НЗД(r0, r1) = … = НЗД(rN−2, rN−1) = rN−1

Пример употребе алгоритма[уреди | уреди извор]

Анимација алгоритма у којој се све мањим квадратима почетни правоугаоник покрива у потпуности. Димензије зеленог правоугаоника су a = 1071 и b = 462. Он се покрива наранџастим квадратима странице 462 све док је то могуће, после чега остане зелени правоугаоник димезија 462×147. Он се затим покрива плавим квадратима дужине страница 147, и као вишак остаје зелени правоугаоник димензија 21×147. Њега је могуће без остатка покрити црвеним квадратима чија је страница дужине 21. То значи да је 21 НЗД бројева 1071 и 462.

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

1071 = 2 × 462 + 147.

Затим се понавља поступак за бројеве 462 и 147 све док нови остатак не постане мањи од 147, што ће се десити после трећег одузимања (q1 = 3), а добијени остатак ће бити 21:

462 = 3 × 147 + 21.

У трећем кораку, 21 се одузима од 147 све док нови остатак не постане мањи од 21. Поступак се може поновити седам пута (q2 = 7) без остатка.

147 = 7 × 21 + 0.

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

Корак k Једнакост Количник и остатак
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; алгоритам се завршава

Визуелизација[уреди | уреди извор]

Еуклидов алгоритам се може и визуелно приказати коришћењем аналогије са прекривањем правоугаоника квадратима.[40] Претпоставка је да је потребно у потпуности прекрити правоугаоник димезија „a пута b“ квадратима, при чему је a дужа страница. Најпре се покушава прекривање квадратима странице b; овај поступак даје непокривен правоугаони вишак димензија „r0 пута b“, при чему је r0<b. Затим се коришћењем квадрата странице r0 прекрива вишак. У том поступку се добија нови непокривени правоугаоник димензија „r1 пута r0“. За његово прекривање се користе квадрати странице r1, итд. Поступак се завршава у тренутку када више нема непокривеног вишка, односно када квадрати покрију правоугаоник у потпуности. Дужина стране најмањег квадрата је НЗД за бројеве који чине странице полазног правоугаоника. На пример, најмањи квадрат на суседној слици је странице 21 (приказан црвеном бојом), а 21 је НЗД бројева 1071 и 462, што су димензије полазног правоугаоника (приказаног зеленом бојом).

Одређивање количника и остатка[уреди | уреди извор]

У сваком кораку k, Еуклидов алгоритам израчунава количник qk и остатак rk помоћу два дата броја rk−1 и rk−2

rk−2 = qk rk−1 + rk

при чему је rk по апсолутној вредности строго мањи од rk−1. Алгоритам дељења обезбеђује да такав количник и остатак увек постоје. Поред тога, алгоритам дељења за природне бројеве тврди да су qk и rk јединствени, али тај услов није потребан Еуклидовом алгоритму.[41]

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

rk rk−2 mod rk−1

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

Имплементације[уреди | уреди извор]

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

function nzd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return 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) је замењено одузимањем које се понавља.[43]

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

Променљиве a и b се смењују у чувању претходних остатака rk−1 и rk−2. Уколико је на почетку итерације a веће од b, онда a добија вредност rk−2, пошто је rk−2 > rk−1. У току извршавања петље a се смањује одузимањем претходног остатка b све док a не постане мање од b. Тада је a следећи остатак rk. Затим се b смањује одузимањем a док не постане мање од њега, и тада постаје једнако rk+1. Процес се наставља док b не постане једнако нули.

Рекурзивна верзија[44] је заснована на једнакости највећег заједничког делиоца сукцесивних остатака и резултата услова на основу кога се излази из петље НЗД(rN−1, 0) = rN−1.

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

Метода најмањих апсолутних остатака[уреди | уреди извор]

Постоји верзија Еуклидовог алгоритма у којој се количник у сваком кораку увећава за један уколико је резултујући негативни остатак по својој апсолутној вредности мањи од типичног позитивног остатка.[45][46] У претходним случајевима, једнакост

rk−2 = qk rk−1 + rk

је претпостављала да важи rk−1 > rk > 0. Међутим, могуће је искористити алтернативни негативни остатак ek:

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

при чему је rk−1 по претпоставци, позитиван број. Ако је |ek| < |rk|, онда се rk замењује са ek. Леополд Кронекер је доказао да се овом методом НЗД одређује у најмањем броју корака у односу на све друге верзије Еуклидовог алгоритма.[45][46]

Други бројевни системи[уреди | уреди извор]

Као што је већ објашњено, Еуклидов алгоритам се користи за одређивање НЗД два природна броја. Међутим, могуће је уопштити га на реалне бројеве, и на егзотичне бројевне системе као што су полиноми, квадратни цели бројеви и Хурвицови кватерниони, те га искористити за показивање основне особине јединствене факторизације, односно чињенице да се такви бројеви моју раставити на јединствен начин на несводљиве елементе који су еквиваленти простих бројева. Јединствена факторизација је кључни услов многих доказа теорије бројева.

Пример[уреди | уреди извор]

НЗД два полинома и налазимо на следећи начин користећи Еуклидов алгоритам (уз скраћивање и проширење):

1.
1a.
2.
2a.
3.

Примене у математици[уреди | уреди извор]

Безуов идентитет[уреди | уреди извор]

Према Безуовом идентитету највећи заједнички делилац, у ознаци g, два цела броја a и b може бити приказан као њихова линеарна комбинација.[47] То значи да је увек могуће одредити целе бројеве s и t да важи једнакост g = sa + tb.[48][49]

Назначени бројеви s и t се могу израчунати помоћу количника q0, q1, итд. променом редоследа једначина у Еуклидовом алгоритму.[50] Почевши са претпоследњом једначином, g се може изразити помоћу количника qN−1 и два претходна остатка, rN−2 и rN−3.

g = rN−1 = rN−3qN−1 rN−2

Наведени остаци могу, аналогно, бити приказани помоћу одговарајућих количника и остатака,

rN−2 = rN−4qN−2 rN−3
rN−3 = rN−5qN−3 rN−4

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

r2 = r0q2 r1
r1 = bq1 r0
r0 = aq0 b

Након што су сви остаци r0, ..., rN замењени, добијена једнакост приказује g као линеарну комбинацију бројева a и b: g = sa + tb. Самим тим, Безуов идентитет, и претходни поступак могу бити генерализовани на контекст еуклидских домена.

Верижни разломци[уреди | уреди извор]

Еуклидов алгоритам је у блиској вези са верижним разломцима.[51] Низ једнакости је могуће записати у облику:

a/b = q0 + r0/b
b/r0 = q1 + r1/r0
r0/r1 = q2 + r2/r1
rk−2/rk−1 = qk + rk/rk−1
rN−2/rN−1 = qN

Последњи члан на десној страни сваке једнакости увек је једнак реципрочној вредности елемента са леве стране следеће једнакости. Из прве две једнакости се добија:

a/b = q0 + 1/(q1 + r1/r0)

Ако се, затим, помоћу треће једнакости замени разломак r1/r0, добија се:

a/b = q0 + 1/(q1 + 1/(q2 + r2/r1))

У сваком кораку, крајњи сабирак у облику разломка rk/rk−1 се увек може заменити употребом следеће једнакости у низу, закључно са последњом. Резултат је верижни разломак

a/b = q0 + 1/(q1 + 1/(q2 + 1/(… + 1/qN))…) = [q0; q1, q2, …, qN]

Како је већ одређен НЗД(1071, 462), и како су израчунати количници qk били редом 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. ^ У савременој употреби, рекло би се да је формулисан за реалне бројеве. Али, како се дужине, површине и запремине, иако се данас представљају реалним бројевима, не изражавају истим мерним јединицама, нити постоји природна јединица за дужину, површину и запремину, у то време није постојала идеја реалних бројева.

Референце[уреди | уреди извор]

  1. ^ Heath, A History Of Greek Mathematics, volume I. стр. 399, 404
  2. ^ Knuth, The Art of Computer Programming, Volume 2. стр. 318.
  3. ^ Еуклид, Елементи, књига VII, тврђење I
  4. ^ Еуклид, Елементи, књига VII, тврђење II
  5. ^ Еуклид, Елементи, књига X, тврђење II
  6. ^ Еуклид, Елементи, књига X, тврђење III
  7. ^ Weil 1994, стр. 46–48
  8. ^ Bartel Leendert van der Waerden (1954). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. стр. 114—115. 
  9. ^ Knuth, The Art of Computer Programming, Volume 2, pp. 318.
  10. ^ von Fritz, K. (1945). „The Discovery of Incommensurability by Hippasus of Metapontum”. Ann. Math. 46: 242—264. doi:10.2307/1969021. 
  11. ^ Heath 1949, стр. 80–83.
  12. ^ Fowler 1987, стр. 31–66.
  13. ^ Becker, O (1933). „Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid”. Quellen und Studien zur Geschichte der Mathematik B. 2: 311—333. 
  14. ^ а б Stillwell, Numbers and Geometry. стр. 31.
  15. ^ а б Tattersall, Elementary number theory in nine chapters. стр. 70.
  16. ^ Rosen, Elementary Number Theory and its Applications. стр. 86–87
  17. ^ Ore, Number Theory and Its History. стр. 247–248
  18. ^ Tattersall, Elementary number theory in nine chapters. стр. 72, 184–185.
  19. ^ Tattersall, Elementary number theory in nine chapters. стр. 72–76
  20. ^ Карл Фридрих Гаус (1832). „Theoria residuorum biquadraticorum”. Comm. Soc. Reg. Sci. Gött. Rec. 4. 
    Види још и Werke, 2:67–148
  21. ^ Stillwell, Numbers and Geometry. стр. 31–32
  22. ^ Dirichlet,Vorlesungen über Zahlentheorie. стр. 29–31
  23. ^ Дедекинд, Рихард (1894). „Supplement XI”. Ур.: Peter Gustav Lejeune Dirichlet. Vorlesungen über Zahlentheorie. 
  24. ^ Stillwell, Elements of Number Theory. стр. 41-42
  25. ^ Jacques Charles François Sturm (1829). „Mémoire sur la résolution des équations numériques”. Bull. des sciences de Férussac. 11: 419—422. 
  26. ^ Jazzing Up Euclid's Algorithm
  27. ^ Integer Relation
  28. ^ Ferguson-Forcade Algorithm
  29. ^ LLL Algorithm
  30. ^ HJLS Algorithm
  31. ^ PSLQ Algorithm
  32. ^ Cole AJ, Davie AJ (1969). „A game based on the Euclidean algorithm and a winning strategy for it”. Math. Gaz. 53: 354—357. doi:10.2307/3612461. 
  33. ^ Rosen, Elementary Number Theory and its Applications. стр. 95.
  34. ^ Roberts, J. (1977). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. стр. 1—8. ISBN 0-262-68028-0. 
  35. ^ Stark, An Introduction to Number Theory. стр. 16–20
  36. ^ Stark, An Introduction to Number Theory. стр. 18.
  37. ^ Stark, An Introduction to Number Theory. стр. 16–20.
  38. ^ Knuth, The Art of Computer Programming, Volume 2. стр. 320.
  39. ^ Lovasz 2003, стр. 100–101
  40. ^ Kimberling, C (1983). „A Visual Euclidean Algorithm”. Mathematics Teacher. 76: 108—109. 
  41. ^ Cohn, Advanced Number Theory. стр. 104–110
  42. ^ Knuth, The Art of Computer Programming, Volume 2. стр. 319–320
  43. ^ Knuth, The Art of Computer Programming, Volume 2. стр. 318–319
  44. ^ Stillwell, Numbers and Geometry. стр. 14.
  45. ^ а б Ore, Number Theory and Its History. стр. 43.
  46. ^ а б Stewart 1964, стр. 43–44
  47. ^ Jones, G. A. & Jones, J. M. (1998). „Bezout's Identity”. Elementary Number Theory. New York: Springer-Verlag. стр. 7–11. 
  48. ^ Rosen, Elementary Number Theory and its Applications. стр. 81.
  49. ^ Cohn, Advanced Number Theory. стр. 104.
  50. ^ Rosen, Elementary Number Theory and its Applications. стр. 91.
  51. ^ Vinogradov 1954, стр. 3–13

Литература[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]