Էվկլիդեսի ալգորիթմ

**Էվկլիդեսի ալգորիթմը** երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու արդյունավետ ալգորիթմ է։ Ալգորիթմը իր անունը ստացել է ի պատիվ հույն մաթեմատիկոս Էվկլիդեսի։ Էվկլիդեսի ալգորիթմի ամենապարզ դեպքը վերաբերվում է երկու ամբողջ դրական թվերի զույգին, որոնցից ձևավորվում է նոր թվերի զույգ, որը կազմված է այդ երկու թվերի փոքրագույնից և մեծագույնի ու փոքրագույնի տարբերությունից։ Գործընթացը շարունակվում է այնքան ժամանակ, քանի դեռ թվերը կդառնան հավասար։ Այդ ստացված թիվն էլ հանդիսանում է տրված երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը։ Այս ալգորիթմի մասին առաջին անգամ նշվել է Էվկլիդես «Սկզբունքներ» գրքում (մոտավորապես մ.թ.ա. 300 թ.)։ Այդ իսկ պատճառով էլ այն համարվում է ամենահին թվային ալգորիթմներից մեկը, որը օգտագործվում է մեր ժամանակներում։ Բայց XIX դարում այն ընդհանրացվել է տարբեր տիպի թվերի համար, ինչպիսիք են՝ Գաուսի ամբողջ թվերը, բազմանդամները։ Որից հետո հանրահաշվում առաջացավ Էվկլիդեսյան օղակ եզրույթը։ Հետագայում Էվկլիդեսյան ալգորիթմը ընդլայնել է իր շրջանակները։
Այս ալգորիթմը ունի շատ տեսական և գործնակնան կիրառություններ։ Այն օգտագործվում է գծային հավասարումների լուծման ժամանակ։ էվկլիդեսյան ալգորիթմը մեծ դեր ունի Ժամանակակից թվերի տեսության թեորեմների ապացույցների ժամանակ։

## Պատմական ակնարկ
Հույն մաթեմատիկոսները այս ալգորիթմը անվանել են  կամ  — «փոխադարձ հանում»։ Այս ալգորիթմը Էվկլիդեսի հայտնագործությունը չէ, քանի որ ալգորիթմի մասին նշել է Արիստոտելը իր «Տոպիկա» տրամաբանական տեսության մեջ։ Իր «Սկզբունքներ» գրքում Էվկլիդեսը այս ալգորիթմին անդրադարձել է երկու անգամ՝ ինչպես գտնել երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը (VII գրքում) և ինչպես որոշել երկու նույն կարգի մեծությունների մեծագույնը (X գրքում)։ Երկու դեպքում էլ տրված է ալգորիթմի երկրաչափական իմաստը։ Պատմաբան մաթեմատիկների կողմից ենթադրվում է, որ հենց Էվկլիդեսի ալգորիթմի օգնությամբ է, որ հույն մաթեմատիկոսները առաջ քաշեցին անսահմանության գաղափարը։ Սակայն, այս ենթադրությունը չունի հստակ փաստաթղթային ապացույց։

## Նկարագրություն
### Էվկլիդեսի ալգգորիթմը ամբողջ թվերի համար
Դիցուք a և b — ամբողջ թվեր են, որոնք միաժամանակ հավասար չեն 0-ի, և այդ թվերի հաջորդականությունը
:  a > b > r_1 > r_2 > r_3 > r_4 > \cdots > r_n
որոշվում է նրանով, որ յուրաքանչյուր r_k — դա նախորդի և վերջինիս նախորդի բաժանումից ստացած մնացորդն է, իսկ նախավերջինը անմնացորդ բաժավում է վերջինի վրա, այսինքն.
: a = bq_0 + r_1, 
: b = r_1q_1 + r_2, 
: r_1 = r_2q_2 + r_3, 
: \cdots
: r_{k-2} = r_{k-1} q_{k-1} + r_k, 
: \cdots
: r_{n-2} = r_{n-1}q_{n-1}+ r_n, 
: r_{n-1} = r_n q_n.

Այսինքն՝ ԱԸԲ (*a*, *b*), ամենամեծ ընդհանուր բաժանարար *a* և *b*, հավասար է *r*n, այդ հաջորդականության վերջին ոչ զրոյական անդամին։.

Այսպիսի *r*1, *r*2, ..., *r*n, հաջորդականության գոյությամբ, կամայական ամբողջ *m* և *n* թվերի համար, որտեղ *m*-ը կամայական ամբողջ թիվ է և ամբողջ *n* ≠ 0 թվերի համար, ապացուցվում է ըստ ինդուկցիայի մեթոդի։
Այսպիսով, կարելի է առանձնացել հետևյալ հետևանքները։
* Դիցուք՝ *a* = *b*⋅*q* + *r*, ապա ԱԸԲ (a, b) = ԱԸԲ (b, r).
* ԱԸԲ (*r*, 0) = *r* յուրաքանչյուր *r*≠ 0 թվի համար (քանի որ 0 բաժանվում է յուրաքանչյուր ամբողջ թվի վրա, բացի 0).

### Էվկլիդեսի ալգորիթմի երկրաչափական իմաստը
Դիցսուք՝ տրված է *a* և *b* հատվածներ։ Հաշվենք այս երկու հատվածների տարբերությունը և մեծ հատվածի արժեքը փոխարինենք ստացված տարբերությամբ։ Կրկնում ենք այս գործողությունը այնքան ժամանակ, քանի դեռ հատվածները կդառնան հավասար։ Եթե ստանում ենք նույն թիվը, ապա հենց այս թիվն էլ հանդիսանում է ամենամեծ ընդհանուր մեծույթունը։ Եթե ընդհանուր մաս չունի, ապա այս գործընթացը անվերջ կարելի է կատարել։ Էվկլիդեսը դիտարկել է այս դեպքը ևս, , որը իրականացվում է կարկինի և քանոնի միջոցով։

## Կիրառություն
### Էվկլիդեսի ալգորիթմի ընդհանրացումը Բեզուի նկատմամբ
Բանաձևերը r_i-ի համար կլինեն հետևյալ կերպ.

: r_1 = a + b(-q_0)
: r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)
: \vdots
: *ԱԸԲ*  (a, b) = r_n = as + bt
Ընդ որում` *s* и *t* ամբողջ թվեր են։ ԱԸԲ-ի այսպիսի ներկայացումը կոչվում է Բեզուի հարաբերակցութուն, իսկ  *s և* *t թվերը`* Բեզուի գործակիցներ։ Հանրահաշվի հիմնական թեորեմի և Էվլիդեսի լեմմայի ապացուցման մեջ էականորեն մեծ դեր ունի Բեզուի հարաբերակցութունը։

### [[Շղթայական կոտորակներ]]
Էվկլիդեսի ալգորիթմը սերտ կապակցված է շղթայական կոտորակների հետ։ *a*/*b ներկայացվում է շղթայական կոտորակների տեսքով հետևյալ կերպ.*
:: \frac ab=[q_0; q_1, q_2, \cdots, q_n].
Ընդ որում՝ շղթայական կոտորակը առանց վերջին անդամի հավասար է Բեզուի գործակիցների հարաբերությանը՝ վերցված բացասական նշանով.

[q_0; q_1, q_2, \cdots, q_{n-1}] = -\frac ts.
:
Հավասարումների հաջորդականությունը, որը ներկայացնում է Էվկլիդեսի ալգորիթմ, կարելի է ներկայացնել հետևյալ տեսքով.
: 
\begin{align}
\frac{a}{b} &= q_0 + \frac{r_0}{b} \\
\frac{b}{r_0} &= q_1 + \frac{r_1}{r_0} \\
\frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\
& {}\ \vdots \\
\frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\
& {}\ \vdots \\
\frac{r_{N-2}}{r_{N-1}} &= q_N
\end{align}

Առաջին երկու հավասարումների միավորումից կունենանք.
: \frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}} 
Հաշվի առնելով երրորդ հավասարությունը, *r*1/*r*0 կոտորակի հայտարարաը փոխարինելով, կունենանք.
: \frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}}} 
Այսպիսով, *r**k*/*r**k*−1 կոտորակը միշտ կարող է փոխարինել հավասարումների հաջորդականության հաջորդ հավասարումով։ Այս գործընթացը կարելի է շարունակել մինչև վերջին հավասարումը։ Արդյունքում կստացվի շղթայական կոտորակ.
: \frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots + \cfrac{1}{q_N}}}} = [ q_0; q_1, q_2, \ldots, q_N ] 

## Ծանոթագրություններ

Կատեգորիա:Ալգորիթմներ
Կատեգորիա:Թվերի տեսություն