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

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

Պատմական ակնարկ

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

Նկարագրություն

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

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

$a>b>r_1>r_2>r_3>r_4>\cdots >r_n$

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

$a=b{q}_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, այդ հաջորդականության վերջին ոչ զրոյական անդամին։Կաղապար:Sfn.

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

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

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

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

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

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

Բանաձևերը $r_i$-ի համար կլինեն հետևյալ կերպ.

$r_1=a+b(-q_0)$

$r_2=b-r_1{q}_1=a(-q_1)+b(1+q_1{q}_0)$

$⋮$

ԱԸԲ $(a,b)=r_n=as+bt$

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

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

Էվկլիդեսի ալգորիթմը սերտ կապակցված է շղթայական կոտորակների հետԿաղապար:Sfn։ 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{array}{cc}\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}\\ & ⋮\\ \frac{r_{k-2}}{r_{k-1}}& =q_k+\frac{r_k}{r_{k-1}}\\ & ⋮\\ \frac{r_{N-2}}{r_{N-1}}& =q_N\end{array}$

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

$\frac{a}{b}=q_0+\frac{1}{q_1+\frac{r_1}{r_0}}$

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

$\frac{a}{b}=q_0+\frac{1}{q_1+\frac{1}{q_2+\frac{r_2}{r_1}}}$

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

$\frac{a}{b}=q_0+\frac{1}{q_1+\frac{1}{q_2+\frac{1}{\ddots +\frac{1}{q_N}}}}=[q_0;q_1,q_2,\dots ,q_N]$