Алгарытм Эўкліда

У матэматыцы **алгарытм Эўкліда** — алгарытм вылічэння найбольшага агульнага дзельніка (НАД) двух (звычайна дадатных) цэлых лікаў. НАД двух цэлых лікаў — найбольшы натуральны лік, які дзеліць іх без астачы. Алгарытм названы так у гонар грэчаскага матэматыка Эўкліда, які апісаў яго ў кнігах VII і X сваіх *Пачаткаў* (каля 300 да н.э.).

У сваёй найпрасцейшай форме Эўклідаў алгарытм пачынае з пары няроўных натуральных лікаў. Новую пару ўтвараюць меншы лік і розніца паміж лікамі старой пары. Так працягваецца, пакуль абодва лікі ў новаўтворанай пары не акажуцца роўнымі, гэтае значэнне і будзе найбольшым агульным дзельнікам. Напрыклад, для 105 і 252 першая ітэрацыя дае пару 105 і 147. Пры паўтарэнні працэдуры атрымліваюцца пары 42 і 105, затым 42 і 63, тады 42 і 21, пакуль лікі ў пары не стануць роўнымі аднаму значэнню, ліку 21, які і ёсць НАД пачатковай пары цэлых лікаў.

Пачаткі апісваюць алгарытм для натуральных лікаў і геаметрычных даўжынь. У 19-м і 20-м стст. былі распрацаваны абагульненні алгарытма Эўкліда. Алгарытм дазваляе эфектыўна прыводзіць дробы да нескарачальнага выгляду. Ён з'яўляецца ключавым элементам у многіх крыптаграфічных алгарытмах і пратаколах, па якіх ажыццяўляецца сувязь паміж вузламі ў абароненых сетках. Нарэшце, Эўклідаў алгарытм можа служыць інструментам для доказу тэарэм у сучаснай тэорыі лікаў і арыфметыцы.

## Апісанне 
Асноўная ідэя алгарытма заключаецца ў тым, што для цэлых лікаў *a* і *b* мноства іх агульных дзельнікаў такое самае, як і мноства агульных дзельнікаў *b* і *a*&nbsp;&minus;&nbsp;*bq* для любога цэлага *q*. І праўда, калі *d* — агульны дзельнік *a* і *b*, то існуюць (па азначэнні дзельніка) цэлыя лікі *e* і *f*, такія што *a*&nbsp;=&nbsp;*ed* і *b*&nbsp;=&nbsp;*fd*. Адсюль вынікае, што *a*&nbsp;&minus;&nbsp;*bq*&nbsp;=&nbsp;*ed*&nbsp;&minus;&nbsp;*fdq*&nbsp;=&nbsp;*d*(*e*&nbsp;&minus;&nbsp;*fq*) і *d* дзеліць *a*&nbsp;&minus;&nbsp;*bq*. Доказ таго, што кожны агульны дзельнік *b* і *a*&nbsp;&minus;&nbsp;*bq* дзеліць таксама *a*, праводзіцца тым жа шляхам: *a*&nbsp;=&nbsp;(*a*&nbsp;&minus;&nbsp;*bq*)&nbsp;+&nbsp;*bq*.

Алгарытм Эўкліда замяняе пару (*a*, *b*) на (*b*, *a*&nbsp;&minus;&nbsp;*bq*) (ад гэтага мноства агульных дзельнікаў не мяняецца) і паўтарае гэтае дзеянне, пакуль урэшце не з'явіцца пара з нулявым лікам. Каб алгарытм гарантавана завяршыўся за канечную колькасць крокаў, лікі *q* выбіраюцца так, каб максімум абсалютных велічынь двух лікаў строга памяншаўся з кожным крокам.

Няхай (*g*, 0) — канчатковы вынік гэтай працэдуры. Мноства агульных дзельнікаў пры гэтым не змянілася, і таму агульныя дзельнікі зыходных лікаў *a* і *b* дакладна такія ж, як і ў лікаў *g* і 0, і такім чынам, супадаюць з дзельнікамі ліку *g* (паколькі *x*·0 = 0 для любых *x*, то 0 дзеліцца на любы цэлы лік). Адпаведна, найбольшы агульны дзельнік лікаў *a* і *b* ёсць *g*, калі *g*&nbsp;>&nbsp;0, і &minus;*g* іначай.

Існуе некалькі варыянтаў алгарытма, якія адрозніваюцца выбарам *q* на кроках.

У першапачатковым Эўклідавым алгарытме мяркуецца, што ўсе лікі дадатныя (адмоўных лікаў тады яшчэ не ведалі), і на кожным кроку найбольшы натуральны лік замяняўся на розніцу лікаў (г.зн. заўсёды выбіралася *q*&nbsp;=&nbsp;1 і, каб першы з лікаў быў большым, пры неабходнасці перамена месцамі). Першапачатковы алгарытм спыняецца, калі атрымліваюцца два роўныя лікі (наступны крок даў бы пару (*g*, 0)). Урэшце рэшт алгарытм завяршыцца, бо найбольшы ў пары лік строга памяншаецца з кожным крокам.

З-за невысокай эфектыўнасці зыходны варыянт Эўклідавага алгарытма ўжываецца толькі ў адукацыйных мэтах. Для практычных вылічэнняў звычайна выкарыстоўваецца варыянт, заснаваны на дзяленні з астачай.

### Дзяленне з астачай 
Дзяленне з астачай — арыфметычная аперацыя, якая для кожнай пары цэлых лікаў *a* і *b*, дзе *b*&nbsp;≠&nbsp;0, дае два цэлыя лікі *q*, *дзель*, і *r*, *астачу*, такія што
: *a*&nbsp;=&nbsp;*bq*&nbsp;+&nbsp;*r* and 0&nbsp;≤&nbsp;*r*&nbsp;*k*&minus;1 і *r**k*&minus;2. Паколькі алгарытм гарантуе, што астаткі з кожным крокам няўхільна памяншаюцца, *r**k*&minus;1 меншы чым яго папярэднік *r**k*&minus;2. Мэта *k*-га кроку — знайсці дзель *q**k* і астатак *r**k* такія, што задавальняецца роўнасць:

: 

дзе *r**k*&nbsp;*k*&minus;1. Іншымі словамі, кратныя меншага ліку *r**k*&minus;1 аднімаюцца ад большага ліку *r**k*&minus;2, пакуль астатак не стане меншы чым *r**k*&minus;1.

На пачатковым кроку (*k*&nbsp;=&nbsp;0) астаткі *r*−2 і *r*−1 раўняюцца *a* і *b*, лікам, для якіх шукаецца НАД. На наступным кроку (*k*&nbsp;=&nbsp;1), астаткі роўныя *b* і астатку *r*0 ад пачатковага кроку, і г.д. Такім чынам, алгарытм можна запісаць наступнай паслядоўнасцю роўнасцей

: 
: 
: 
: 
: 

Каля лік *a* меншы за *b*, першы крок алгарытма проста мяняе лікі месцамі. Напрыклад, калі *a*&nbsp;0 раўняецца нулю, а астатак *r*0 роўны *a*. Такім чынам, *r**k* меншы чым яго папярэднік *r**k*−1 для любых *k*&nbsp;≥&nbsp;0.

Паколькі астаткі памяншаюцца з кожным крокам і пры гэтым заўсёды неадмоўныя, у рэшце рэшт на нейкім кроку астатак *r**N* павінен аказацца роўным нулю, на гэтым кроку алгарытм спыняецца. Апошні ненулявы астатак *r**N*−1 і ёсць найбольшы агульны дзельнік *a* і *b*. Нумар кроку *N* абавязкова канечны, бо існуе толькі канечная колькасць неадмоўных цэлых лікаў паміж пачатковым астаткам *r*0 і нулём.

У псеўдакодзе алгарытм можна запісаць так (улічваючы, што дзелі *q**i* не выкарыстоўваюцца яўна):
 **function** gcd(*a*, *b*)
     *r*0 := *a*
     *r*1 := *b*
     *i* := 1
     **while** *r**i* ≠ 0
        *r**i*+1 := *r**i*-1 **mod** *r**i*
        *i* := *i* + 1
     **if** *i* ≤ 2 **then return** |*r**i*-1|
     **return** *r**i*-1

Перадапошні радок патрэбен на выпадак, калі апошні ненулявы астатак роўны *a* ці *b*, якія могуць аказацца адмоўнымі, калі ўваходныя параметры працэдуры не абмяжоўваюцца дадатнымі лікамі.

Запіс алгарытма можна яшчэ больш спрасціць, бо захоўваць прамежкавыя астаткі няма патрэбы (тут мяркуецца, што ўваходныя лікі неадмоўныя):

 **function** gcd(*a*, *b*)
     **while** *b* ≠ 0
        *r* := *a* **mod** *b*
        *a* := *b*
        *b* := *r*
     **return** *a*

### Лікавы прыклад 
upright|thumb|alt=Анімацыя, на якой паступова меншыя квадраты дабаўляюцца, каб поўнасцю пакрыць прамавугольнік.|Анімаваная ілюстрацыя алгарытма Эўкліда, заснаванага на адыманні. Пачатковы зялёны прамавугольнік мае памеры *a*&nbsp;=&nbsp;1071 і *b*&nbsp;=&nbsp;462. Квадратныя памерам 462&times;462 аранжавыя пліткі дабаўляюцца пакуль не застанецца зялёны 462&times;147 прамавугольнік. Зялёны 462&times;147 прамавугольнік пакрываецца квадратнымі 147&times;147 сінімі пліткамі, пакуль не застаецца зялёны 21&times;147 прамавугольнік. Зялёны 21&times;147 прамавугольнік поўнасцю пакрываецца квадратнымі 21&times;21 чырвонымі пліткамі. Такім чынам, 21 ёсць найбольшы агульны дзельнік 1071 і 462.

Каб праілюстраваць алгарытм Эўкліда, знойдзем найбольшы агульны дзельнік лікаў *a*&nbsp;=&nbsp;1071 і *b*&nbsp;=&nbsp;462. Спачатку лік 462 аднімаецца ад 1071 некалькі разоў, пакуль астатак не стане меншы за 462. Такіх адніманняў будзе два (*q*0&nbsp;=&nbsp;2), у астатку застанецца 147

: 

Затым кратныя 147 аднімаюцца ад 462, пакуль астатак не стане меншы за 147. Такіх адніманняў спатрэбіцца тры (*q*1&nbsp;=&nbsp;3), астатак будзе 21

: 

Потым кратныя 21 аднімаюцца ад 147, пакуль у астатку не застанецца менш чым 21. Такіх адніманняў будзе сем (*q*2&nbsp;=&nbsp;7), пры гэтым у астатку нічога не застанецца

: 

Раз апошні астатак нулявы, алгарытм завяршаецца, даючы лік 21 як найбольшы агульны дзельнік лікаў 1071 і 462. Праверыць адказ можна, вылічыўшы НАД(1071, 462) праз разкладанне лікаў на простыя множнікі. Пройдзеныя крокі можна прадставіць табліцай

### Візуалізацыя 
Алгарытм Эўкліда можна візуалізаваць з дапамогай пакрыцця прамавугольнікаў квадратнымі пліткамі. Дапусцім, што трэба роўна пакрыць *a*-на-*b*-прамавульнік квадратнымі пліткамі. Няхай *a* — большы з двух лікаў. Спачатку спрабуем залажыць прамавугольнік квадратнымі пліткамі *b*-на-*b*. Але застаецца непакрыты астаткавы *r*0-на-*b* прамавугольнік, дзе *r*0&nbsp;0-на-*r*0. Застаецца другі астаткавы прамавугольнік *r*1-на-*r*0, які мы спрабуем залажыць квадратамі *r*1-на-*r*1, і г.д. Паслядоўнасць заканчваецца, калі не застаецца астаткавага прамавугольніка, г.зн. квадратныя пліткі роўна пакрываюць папярэдні астаткавы прамавугольнік. Даўжыня старон найменшай квадратнай пліткі і ёсць НАД даўжынь старон пачатковага прамавугольніка. Напрыклад, самая маленькая квадратная плітка на суседнім рысунку мае памер 21-на-21 (паказана чырвоным), і 21 ёсць НАД лікаў 1071 і 462, памераў пачаткова прамавугольніка (на рысунку зялёны).

### Варыянт з найменшымі абсалютнымі астаткамі 
Варыянт дзялення з астаткам, т.зв. *дзяленне з найменшым абсалютным астаткам*, заключаецца ў дапушчэнні адмоўных астаткаў і выбары дзелі такім чынам, каб астатак меў як мага меншую абсалютную велічыню. Пры такім дзяленні для кожнай пары цэлых лікаў *a* і *b* такіх, што *b*&nbsp;≠&nbsp;0, існуе роўна адна пара цэлых *q* і *r*, такіх што
: *a*&nbsp;=&nbsp;*bq*&nbsp;+&nbsp;*r* &nbsp;&nbsp;і&nbsp;&nbsp;&minus;&nbsp;<&nbsp;*r*&nbsp;≤&nbsp;,
дзе |*b*| абазначае абсалютную велічыню ліку *b* (г.зн. *b*, калі *b* дадатны, і &minus;*b* іначай).

Такое дзяленне лёгка выводзіцца са звычайнага дзялення з астачай. Калі ''q' * і *r' * — дзель і астатак звычайнага дзялення з астачай, тады бяром  і , калі , а іначай  і , дзе  пры , і  пры .

У астатнім такі варыянт алгарытма Эўкліда нічым не адрозніваецца ад звычайнага: дастаткова толькі змяніць азначэнне аперацыі «mod» так, каб яна выдавала найменшы абсалютны астатак, і мяняць знак выніку, калі ён адмоўны.

Леапольд Кронекер паказаў, што гэты варыянт патрабуе найменшую колькасць крокаў у параўнанні з любой іншай версіяй алгарытма Эўкліда (г.зн. для любога іншага выбару *q* і *r'').

## Зноскі 
## Літаратура 
* 
* 
* 
* 
* 
* 
* 
* 

Катэгорыя:Алгарытмы
Катэгорыя:Тэорыя лікаў
Катэгорыя:Дзяленне