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

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

Էվկլիդեսի ալգորիթմ
Տեսակ	ալգորիթմ
Անվանված է	Էվկլիդես

Հույն մաթեմատիկոսները այս ալգորիթմը անվանել են ἀνθυφαίρεσις կամ ἀνταναίρεσις — «փոխադարձ հանում»։ Այս ալգորիթմը Էվկլիդեսի հայտնագործությունը չէ, քանի որ ալգորիթմի մասին նշել է Արիստոտելը իր «Տոպիկա» տրամաբանական տեսության մեջ։ Իր «Սկզբունքներ» գրքում Էվկլիդեսը այս ալգորիթմին անդրադարձել է երկու անգամ՝ ինչպես գտնել երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը (VII գրքում) և ինչպես որոշել երկու նույն կարգի մեծությունների մեծագույնը (X գրքում)։ Երկու դեպքում էլ տրված է ալգորիթմի երկրաչափական իմաստը։ Պատմաբան մաթեմատիկների կողմից ենթադրվում է, որ հենց Էվկլիդեսի ալգորիթմի օգնությամբ է, որ հույն մաթեմատիկոսները առաջ քաշեցին անսահմանության գաղափարը։ Սակայն, այս ենթադրությունը չունի հստակ փաստաթղթային ապացույց։

Էվկլիդեսի ալգգորիթմը ամբողջ թվերի համար

Դիցուք ${\displaystyle a}$  և ${\displaystyle b}$  — ամբողջ թվեր են, որոնք միաժամանակ հավասար չեն 0-ի, և այդ թվերի հաջորդականությունը

${\displaystyle a>b>r_{1}>r_{2}>r_{3}>r_{4}>\cdots >r_{n}}$ 

որոշվում է նրանով, որ յուրաքանչյուր ${\displaystyle r_{k}}$  — դա նախորդի և վերջինիս նախորդի բաժանումից ստացած մնացորդն է, իսկ նախավերջինը անմնացորդ բաժավում է վերջինի վրա, այսինքն.

${\displaystyle a=bq_{0}+r_{1},}$ 
${\displaystyle b=r_{1}q_{1}+r_{2},}$ 
${\displaystyle r_{1}=r_{2}q_{2}+r_{3},}$ 
${\displaystyle \cdots }$ 
${\displaystyle r_{k-2}=r_{k-1}q_{k-1}+r_{k},}$ 
${\displaystyle \cdots }$ 
${\displaystyle r_{n-2}=r_{n-1}q_{n-1}+r_{n},}$ 
${\displaystyle r_{n-1}=r_{n}q_{n}.}$ 

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

Այսպիսի r₁, r₂, ..., r_n, հաջորդականության գոյությամբ, կամայական ամբողջ m և n թվերի համար, որտեղ m-ը կամայական ամբողջ թիվ է և ամբողջ n ≠ 0 թվերի համար, ապացուցվում է ըստ ինդուկցիայի մեթոդի։ Այսպիսով, կարելի է առանձնացել հետևյալ հետևանքները։

• Դիցուք՝ a = b⋅q + r, ապա ԱԸԲ (a, b) = ԱԸԲ (b, r).
• ԱԸԲ (r, 0) = r յուրաքանչյուր r≠ 0 թվի համար (քանի որ 0 բաժանվում է յուրաքանչյուր ամբողջ թվի վրա, բացի 0).

Էվկլիդեսի ալգորիթմի երկրաչափական իմաստը

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

Էվկլիդեսի ալգորիթմի ընդհանրացումը Բեզուի նկատմամբ

Բանաձևերը ${\displaystyle r_{i}}$ -ի համար կլինեն հետևյալ կերպ.

${\displaystyle r_{1}=a+b(-q_{0})}$ 
${\displaystyle r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})}$ 
${\displaystyle \vdots }$ 
ԱԸԲ ${\displaystyle (a,b)=r_{n}=as+bt}$ 

Ընդ որում` s и t ամբողջ թվեր են։ ԱԸԲ-ի այսպիսի ներկայացումը կոչվում է Բեզուի հարաբերակցութուն, իսկ s և t թվերը` Բեզուի գործակիցներ։ Հանրահաշվի հիմնական թեորեմի և Էվլիդեսի լեմմայի ապացուցման մեջ էականորեն մեծ դեր ունի Բեզուի հարաբերակցութունը։

Շղթայական կոտորակներ

Էվկլիդեսի ալգորիթմը սերտ կապակցված է շղթայական կոտորակների հետ։ a/b ներկայացվում է շղթայական կոտորակների տեսքով հետևյալ կերպ.

${\displaystyle {\frac {a}{b}}=[q_{0};q_{1},q_{2},\cdots ,q_{n}]}$ .

Ընդ որում՝ շղթայական կոտորակը առանց վերջին անդամի հավասար է Բեզուի գործակիցների հարաբերությանը՝ վերցված բացասական նշանով.

${\displaystyle [q_{0};q_{1},q_{2},\cdots ,q_{n-1}]=-{\frac {t}{s}}}$ .

Հավասարումների հաջորդականությունը, որը ներկայացնում է Էվկլիդեսի ալգորիթմ, կարելի է ներկայացնել հետևյալ տեսքով.

${\displaystyle {\begin{aligned}{\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{aligned}}}$ 

Առաջին երկու հավասարումների միավորումից կունենանք.

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}}$ 

Հաշվի առնելով երրորդ հավասարությունը, r₁/r₀ կոտորակի հայտարարաը փոխարինելով, կունենանք.

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}}$ 

Այսպիսով, r_k/r_k−1 կոտորակը միշտ կարող է փոխարինել հավասարումների հաջորդականության հաջորդ հավասարումով։ Այս գործընթացը կարելի է շարունակել մինչև վերջին հավասարումը։ Արդյունքում կստացվի շղթայական կոտորակ.

${\displaystyle {\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}]}$