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

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


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


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


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

  
    
      
        a
        >
        b
        >
        
          r
          
            1
          
        
        >
        
          r
          
            2
          
        
        >
        
          r
          
            3
          
        
        >
        
          r
          
            4
          
        
        >
        ⋯
        >
        
          r
          
            n
          
        
      
    
    {\displaystyle a>b>r_{1}>r_{2}>r_{3}>r_{4}>\cdots >r_{n}}
  որոշվում է նրանով, որ յուրաքանչյուր 
  
    
      
        
          r
          
            k
          
        
      
    
    {\displaystyle r_{k}}
   — դա նախորդի և վերջինիս նախորդի բաժանումից ստացած մնացորդն է, իսկ նախավերջինը անմնացորդ բաժավում է վերջինի վրա, այսինքն.

  
    
      
        a
        =
        b
        
          q
          
            0
          
        
        +
        
          r
          
            1
          
        
        ,
      
    
    {\displaystyle a=bq_{0}+r_{1},}
  

  
    
      
        b
        =
        
          r
          
            1
          
        
        
          q
          
            1
          
        
        +
        
          r
          
            2
          
        
        ,
      
    
    {\displaystyle b=r_{1}q_{1}+r_{2},}
  

  
    
      
        
          r
          
            1
          
        
        =
        
          r
          
            2
          
        
        
          q
          
            2
          
        
        +
        
          r
          
            3
          
        
        ,
      
    
    {\displaystyle r_{1}=r_{2}q_{2}+r_{3},}
  

  
    
      
        ⋯
      
    
    {\displaystyle \cdots }
  

  
    
      
        
          r
          
            k
            −
            2
          
        
        =
        
          r
          
            k
            −
            1
          
        
        
          q
          
            k
            −
            1
          
        
        +
        
          r
          
            k
          
        
        ,
      
    
    {\displaystyle r_{k-2}=r_{k-1}q_{k-1}+r_{k},}
  

  
    
      
        ⋯
      
    
    {\displaystyle \cdots }
  

  
    
      
        
          r
          
            n
            −
            2
          
        
        =
        
          r
          
            n
            −
            1
          
        
        
          q
          
            n
            −
            1
          
        
        +
        
          r
          
            n
          
        
        ,
      
    
    {\displaystyle r_{n-2}=r_{n-1}q_{n-1}+r_{n},}
  

  
    
      
        
          r
          
            n
            −
            1
          
        
        =
        
          r
          
            n
          
        
        
          q
          
            n
          
        
        .
      
    
    {\displaystyle r_{n-1}=r_{n}q_{n}.}
  Այսինքն՝ ԱԸԲ (a, b), ամենամեծ ընդհանուր բաժանարար a և b, հավասար է rn, այդ հաջորդականության վերջին ոչ զրոյական անդամին։.
Այսպիսի r1, r2, ..., rn, հաջորդականության գոյությամբ, կամայական ամբողջ m և n թվերի համար, որտեղ m-ը կամայական ամբողջ թիվ է և ամբողջ n ≠ 0 թվերի համար, ապացուցվում է ըստ ինդուկցիայի մեթոդի։
Այսպիսով, կարելի է առանձնացել հետևյալ հետևանքները։

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


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


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


=== Էվկլիդեսի ալգորիթմի ընդհանրացումը Բեզուի նկատմամբ ===
Բանաձևերը 
  
    
      
        
          r
          
            i
          
        
      
    
    {\displaystyle r_{i}}
  -ի համար կլինեն հետևյալ կերպ.

  
    
      
        
          r
          
            1
          
        
        =
        a
        +
        b
        (
        −
        
          q
          
            0
          
        
        )
      
    
    {\displaystyle r_{1}=a+b(-q_{0})}
  

  
    
      
        
          r
          
            2
          
        
        =
        b
        −
        
          r
          
            1
          
        
        
          q
          
            1
          
        
        =
        a
        (
        −
        
          q
          
            1
          
        
        )
        +
        b
        (
        1
        +
        
          q
          
            1
          
        
        
          q
          
            0
          
        
        )
      
    
    {\displaystyle r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})}
  

  
    
      
        ⋮
      
    
    {\displaystyle \vdots }
  
ԱԸԲ 
  
    
      
        (
        a
        ,
        b
        )
        =
        
          r
          
            n
          
        
        =
        a
        s
        +
        b
        t
      
    
    {\displaystyle (a,b)=r_{n}=as+bt}
  Ընդ որում` s и t ամբողջ թվեր են։ ԱԸԲ-ի այսպիսի ներկայացումը կոչվում է Բեզուի հարաբերակցութուն, իսկ  s և t թվերը` Բեզուի գործակիցներ։ Հանրահաշվի հիմնական թեորեմի և Էվլիդեսի լեմմայի ապացուցման մեջ էականորեն մեծ դեր ունի Բեզուի հարաբերակցութունը։


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

  
    
      
        
          
            a
            b
          
        
        =
        [
        
          q
          
            0
          
        
        ;
        
          q
          
            1
          
        
        ,
        
          q
          
            2
          
        
        ,
        ⋯
        ,
        
          q
          
            n
          
        
        ]
      
    
    {\displaystyle {\frac {a}{b}}=[q_{0};q_{1},q_{2},\cdots ,q_{n}]}
  .Ընդ որում՝ շղթայական կոտորակը առանց վերջին անդամի հավասար է Բեզուի գործակիցների հարաբերությանը՝ վերցված բացասական նշանով.

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

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

  
    
      
        
          
            
              
                
                  
                    a
                    b
                  
                
              
              
                
                =
                
                  q
                  
                    0
                  
                
                +
                
                  
                    
                      r
                      
                        0
                      
                    
                    b
                  
                
              
            
            
              
                
                  
                    b
                    
                      r
                      
                        0
                      
                    
                  
                
              
              
                
                =
                
                  q
                  
                    1
                  
                
                +
                
                  
                    
                      r
                      
                        1
                      
                    
                    
                      r
                      
                        0
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      r
                      
                        0
                      
                    
                    
                      r
                      
                        1
                      
                    
                  
                
              
              
                
                =
                
                  q
                  
                    2
                  
                
                +
                
                  
                    
                      r
                      
                        2
                      
                    
                    
                      r
                      
                        1
                      
                    
                  
                
              
            
            
              
              
                

                
                 
                ⋮
              
            
            
              
                
                  
                    
                      r
                      
                        k
                        −
                        2
                      
                    
                    
                      r
                      
                        k
                        −
                        1
                      
                    
                  
                
              
              
                
                =
                
                  q
                  
                    k
                  
                
                +
                
                  
                    
                      r
                      
                        k
                      
                    
                    
                      r
                      
                        k
                        −
                        1
                      
                    
                  
                
              
            
            
              
              
                

                
                 
                ⋮
              
            
            
              
                
                  
                    
                      r
                      
                        N
                        −
                        2
                      
                    
                    
                      r
                      
                        N
                        −
                        1
                      
                    
                  
                
              
              
                
                =
                
                  q
                  
                    N
                  
                
              
            
          
        
      
    
    {\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}}}
  Առաջին երկու հավասարումների միավորումից կունենանք.

  
    
      
        
          
            a
            b
          
        
        =
        
          q
          
            0
          
        
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  
                    q
                    
                      1
                    
                  
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            
                              r
                              
                                1
                              
                            
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            
                              r
                              
                                0
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    {\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}}
  Հաշվի առնելով երրորդ հավասարությունը, r1/r0 կոտորակի հայտարարաը փոխարինելով, կունենանք.

  
    
      
        
          
            a
            b
          
        
        =
        
          q
          
            0
          
        
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  
                    q
                    
                      1
                    
                  
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            1
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            
                              q
                              
                                2
                              
                            
                            +
                            
                              
                                
                                  
                                    
                                  
                                  
                                    
                                      
                                        r
                                        
                                          2
                                        
                                      
                                    
                                  
                                
                                
                                  
                                    
                                  
                                  
                                    
                                      
                                        r
                                        
                                          1
                                        
                                      
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    {\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}}
  Այսպիսով, rk/rk−1 կոտորակը միշտ կարող է փոխարինել հավասարումների հաջորդականության հաջորդ հավասարումով։ Այս գործընթացը կարելի է շարունակել մինչև վերջին հավասարումը։ Արդյունքում կստացվի շղթայական կոտորակ.

  
    
      
        
          
            a
            b
          
        
        =
        
          q
          
            0
          
        
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  
                    q
                    
                      1
                    
                  
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            1
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            
                              q
                              
                                2
                              
                            
                            +
                            
                              
                                
                                  
                                    
                                  
                                  
                                    
                                      1
                                    
                                  
                                
                                
                                  
                                    
                                  
                                  
                                    
                                      ⋱
                                      +
                                      
                                        
                                          
                                            
                                              
                                            
                                            
                                              
                                                1
                                              
                                            
                                          
                                          
                                            
                                              
                                            
                                            
                                              
                                                
                                                  q
                                                  
                                                    N
                                                  
                                                
                                              
                                            
                                          
                                        
                                      
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
        =
        [
        
          q
          
            0
          
        
        ;
        
          q
          
            1
          
        
        ,
        
          q
          
            2
          
        
        ,
        …
        ,
        
          q
          
            N
          
        
        ]
      
    
    {\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}]}
  


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