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

мини|325x325пкс| Анимација на Евклидовиот алгоритам за броевите 252 и 105. Единичните сегменти се всушност со должина 21, што е најголемиот заеднички делител (НЗД) на дадените броеви. Во секој чекор, помалиот број се одзема од поголемиот, додека еден од нив не се сведе на нула. Останатите се појдовни броеви на НЗД. Евклидов алгоритам — ефикасен начин во математиката, за одредување на најголемиот заеднички делител (НЗД) на дадените броеви. Алгоритмот е именуван по старогрчкиот математичар Евклид, кој го спомнал во својата книга Елементи.Heath, A History Of Greek Mathematics, volume I. стр. 399, 404

НЗД на два броја е најголемиот број што истовремено ги дели и двата броја без остаток. Евклидовиот алгоритам се заснова на начелото дека најголемиот заеднички делител на два броја не се менува ако помалиот број се одземе од поголемиот број, а потоа се определи НЗД на новодобиениот број и помалиот од претходните два. На пример, 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 век , биле развиени методи за подобрување на ефикасноста на Евклидовиот алгоритам.

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

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

Со векови подоцна, Евклидовиот алгоритам бил повторно откриен независно во Индија и Кина,Stillwell, Numbers and Geometry. стр. 31. првенствено како средство за одредување решенија за диофантските равенки кои се појавиле при решавање на астрономски проблеми и правење точни календари. Во втората половина на петтиот век, индискиот математичар и астроном Ариабхата го опишал алгоритамот како „дробилка“,Tattersall, Elementary number theory in nine chapters. стр. 70. можеби поради неговата ефикасност во решавањето на диофантските равенки.Rosen, Elementary Number Theory and its Applications. стр. 86–87 Иако како посебен случај кинеската теорема за остатоци веќе била наведена од кинескиот математичар и астроном Сун-цуOre, стр. 247–248 во 5 век од нашата ера, општото решение во 1247 година го објавил Чин Чу-шао во неговото дело Цзју чжан суан шу (, Девет книги за математичката вештина).Tattersall, Elementary number theory in nine chapters. стр. 72, 184–185.

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

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

Се чини дека Дирихле бил првиот автор кој го сметал Евклидовиот алгоритам како еден од основните елементи на теоријата на броеви.Stillwell, Numbers and Geometry. стр. 31–32 Тој забележал дека многу од резултатите од теоријата на броеви (на пример, единствена факторизација) би биле вистинити во кој било друг броен систем каде што може да се примени Евклидовиот алгоритам.Dirichlet,. стр. 29–31 Предавањата на Дирихле за теоријата на броеви биле дополнети и ревидирани од Рихард Дедекинд, кој го користел Евклидовиот алгоритам за проучување на нов општ вид на броеви - алгебарски цели броеви. Тој бил првиот што ја докажал теоремата на Ферма за збир на два квадрати користејќи ја единствената факторизација на Гаусови цели броеви. Дополнително, Дедекинд го дефинирал и концептот на Евклидовиот домен, броен систем во кој е можно да се дефинира обопшувањето на Евклидовиот алгоритам. На крајот на 19 век, Евклидовиот алгоритам бил постепено занемарен во корист на поопштата теорија за идеалите на Дедекинд.Stillwell, Numbers and Geometry. стр. 41-42 „Евклидовиот алгоритам е покривката на сите алгоритми, бидејќи е најстариот преживеан нетривијален алгоритам. " Доналд Кнут, (1981). стр. 318. Процесот на наоѓање апликации на Евклидовиот алгоритам, кој започнал во 19 век, продолжил до ден-денес. Шарл Штурм во 1829 година покажал дека алгоритмот може да се користи во Штурмовата верига, што се користи за броење на реалните нули на полином во произволно избран интервал.

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

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

Алгоритам

Начело Евклидовиот алгоритам има итеративна природа, што значи дека конечниот резултат се добива во низа чекори, додека меѓурезалтатот од произволен чекор се користи во првиот следен чекор.Stark, An Introduction to Number Theory. стр. 16–20 Ако k e цел број што се користи за означување на чекорите на алгоритмот почнувајќи од нула е еднаков, тогаш на првиот чекор му одговара  k= 0, на вториот k = 1, и така натаму.

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

rk−2 = qk rk−1 + rk

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

Во првиот чекор ( = 0), остатоците −2 и −1 се еднакви и соодветно, и тоа се токму броевите за кои се бара НЗД. Во следниот чекор ( = 1), остатоците стануваат еднакви на остатокот од почетниот чекор... Врз основа на ова, алгоритмот може да биде претставен со низа еднаквости: 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 мора да стане еднаков на нула во одреден момент, и тогаш алгоритмот запира.Старк, An Introduction to Number Theory. стр. 18. Последниот остаток rN−1 што се разликува од нула е најголемиот заеднички делител за броевите a и b. Бројот N не може да биде бесконечен бидејќи помеѓу нула и првиот остаток r0 постои конечен број на ненегативни цели броеви.

Доказ на валидноста Валидноста на Евклидовиот алгоритам може да се докаже во два чекори.Stark, An Introduction to Number Theory. стр. 16–20. Во првиот чекор, се покажува дека последниот rN−1 е различен од нула и истовремено ги дели a и b. Бидејќи е заеднички делител, мора да биде помал или еднаков на најголемиот заеднички делител g. Во вториот чекор, се покажува дека произволен заеднички делител на броевите a и b, вклучувајќи го и g, мора да го дели rN−1; оттука следи дека g мора да биде помал или еднаков на rN−1. Двата добиени заклучоци се конзистентни само во случај кога rN−1 = g.

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