Մասնակից:Արմինե Չատինյան/Ավազարկղ 2

Էվկլիդեսի ալգորիթմ — երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու արդյունավետ ալգորիթմ: Ալգորիթմը իր անունը ստացել է ի պատիվ հույն մաթեմատիկոս Էվկլիդեսի: Էվկլիդեսի ալգորիթմի ամենապարզ դեպքը վերաբերվում է երկու ամբողջ դրական թվերի զույգին, որոնցից ձևավորվում է նոր թվերի զույգ, որը կազմված է այդ երկու թվերի փոքրագույնից և մեծագույնի ու փոքրագույնի տարբերությունից: Գործընթացը շարունակվում է այնքան ժամանկ, քանի դեռ թվերը կդառնան հավասար: Այդ ստացված թիվն էլ հանդիսանում է տրված երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը: Այս ալգորիթմի մասին առաջին անգամ նշվել է Էվկլիդեսի «Սկզբունքներ» գրքում (մոտավորապես Ք.ա. 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_{1}q_{1}+r_{2},$

$r_{1}=r_{2}q_{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₁, 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հատվածներ: Հաշվենք այս երկու հատվածների տարբերությունը և մեծ հատվածի արժեքը փոխարինենք ստացված տարբերությամբ: Կրկնում ենք այս գործողությունը այնքան ժամանակ, քանի դեռ հատվածները կդառնան հավասար: Եթե ստանում ենք նույն թիվը, ապա հենց այս թիվն էլ հանդիսանում է ամենամեծ ընդհանուր մեծքույթունը: Եթե ընդհանուր մաս չունի, ապա այս գործընթացը անվերջ կարելի է կատարել: Էվկլիդեսը դիտարկել է այս դեպքը ևս, , որը իրականացվում է կարկինի և քանոնի միջոցով:

Կիրառություն

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

Բանաձևերը $r_{i}$ի համար կլինեն հետևյալ կերպ. могут быть переписаны следующим образом:

$r_{1}=a+b(-q_{0})$

$r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})$

$\vdots$

ԱԸԲ $(a,b)=r_{n}=as+bt$

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

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

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

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

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

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

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

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

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

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

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

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