ユークリッドアルゴリズム

ユークリッドアルゴリズム
ユークリッドアルゴリズムはまた、2つの整数a、bの最大公約数を計算するための転々相除算とも呼ばれる.その計算原理は以下の定理に依存する.
定理:gcd(a,b)=gcd(b,a mod b)

   ：a     a = kb + r， r = a mod b

   d a,b      ，  

 d|a, d|b， r = a - kb，  d|r

   d (b,a mod b)    

 

   d  (b,a mod b)    ， 

 d | b , d |r ，  a = kb +r 

   d  (a,b)    

 

   (a,b) (b,a mod b)        ，           ，  

-----------------------------------------------------------------

 P    
    a、p，      b，  ab mod p =1，  ，b a  p    。
  ：a   p           gcd(a,p) = 1
   ：

        

   gcd(a,p) = 1，  オーラの  ，aφ(p) ≡ 1 mod p，  

   aφ(p)-1 mod p a  p    。

 

       

     a p      b

 ab ≡ 1 mod p

  ab = kp +1    ，  1 = ab - kp

   gcd(a,p) = d 

   d | 1

   d   1

-----------------------------------------------------------------------
        
             (a,b)      ，     a b b a     ， C      ： 
 intgcd(inta,intb,int&ar,int&br)

 {

  intx1,x2,x3;

  inty1,y2,y3;

  intt1,t2,t3;

  if(0==a)

  {//     0，        

   ar=0;

   br=0;

   returnb;

  }

  if(0==b)

  {

   ar=0;

   br=0;

   returna;

  }

  x1=1;

  x2=0;

  x3=a;

  y1=0;

  y2=1;

  y3=b;

  intk;

  for(t3=x3%y3;t3!=0;t3=x3%y3)

  {

   k=x3/y3;

   t2=x2-k*y2;

   t1=x1-k*y1;

   x1=y1;

   x1=y2;

   x3=y3;

   y1=t1;

   y2=t2;

   y3=t3;

  }

  if(y3==1)

  {

   //     

   ar=y2;

   br=x1;

   return1;

  }else{

  //     1，     

   ar=0;

   br=0;

   returny3;

  }

 }

  ユークリッドアルゴリズムは、     の  と  のユークリッドアルゴリズムとが  している. け の   を  すると かりにくいです. を  する  を30  えた.まず、    するの の つの  を り す.gcd(a,b)＝dであれば、m,nが  し、d＝ma＋nnが  する.この  をa、bの み わせ  d、m、nと ぶ.d=1の  、m a+n b=1があり、この  、mはa bの    であり、nはb aの    であることがわかる.  の  を  するために、  の  におけるxi、yiをtiの     と なし、  の (t 1、t 2、t 3)を  し、   で  します.ユークリッドアルゴリズムを  して  した  、どの もaを  させます.×t 1+b×t 2=t 3 
    ：1 × a + 0 × b = a  

    ：0 × a + 1 × b = b  

    k    ，   k+1 

   k-1  k  

 t1(k-1)    t2(k-1)  t3(k-1)

 t1(k)      t2(k)    t3(k)

     ：

 t1(k-1) × a + t2(k-1) × b = t3(k-1)

 t1(k)   × a + t2(k)   × b = t3(k)

           ，  t3(k-1) = j t3(k) + r

  ：

  t3(k+1) = r

  t2(k+1) = t2(k-1) - j × t2(k)

  t1(k+1) = t1(k-1) - j × t1(k)

  

         t1(k+1) × a + t2(k+1) × b 

        =t1(k-1) × a - j × t1(k) × a +

         t2(k-1) × b - j × t2(k) × b

       = t3(k-1) - j t3(k) = r 

       = t3(k+1)

   

  ，   t3     1 ， t1× a + t2 × b = 1，  ，t1 a b     ，t2 b a     。