ユークリッドアルゴリズムと拡張ユークリッドアルゴリズム

 
ユークリッドアルゴリズムユークリッドアルゴリズムは、2つの整数a,bの最大公約数を計算するために、転がり相除去法とも呼ばれる.その計算原理は以下の定理に依存する:定理:gcd(a,b)=gcd(b,a mod b)は、aがa=kb+rとして表すことができ、r=a mod bはdがa,bの1つの公約数であると仮定し、d|a,d|bがあり、r=a−kbであるため、d|rは(b,a mod b)の公約数であると仮定し、d|b,d|rである.しかし、a=kb+rであるため、dも(a,b)の公約数であるため(a,b)と(b,a mod b)の公約数は同じであり、その最大公約数も必然的に等しい.ユークリッドアルゴリズムはこの原理に基づいて行われていることを証明し、そのアルゴリズムはC++言語で記述されている.
 

void swap(int & a, int & b)
 {
     int c = a;
     a = b;
     b = c;
 }
 int gcd(int a,int b)
 {
     if(0 == a )
     {
          return b;
     }
     if( 0 == b)
    {
          return a;
     }
     if(a > b)
    {
          swap(a,b);
     }
     int c;
     for(c = a % b ; c > 0 ; c = a % b)
    {
          a = b;
          b = c;
    }
    return 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(φ(p)は{0,1,...,p−1}の中でどれだけの整数が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であるしかない
 
 
ユークリッドアルゴリズム:
 
(1)反復バージョン
 
[cpp] view plaincopy

int ITERATIVE-GCD(int a, int b) {  

   int r = a % b;  

   while (r) {  

     a = b;  

     b = r;  

     r = a % b;  

   }  

   return b;  

}       

 
(2)再帰版
 
[cpp] view plaincopy

int RECURSIVE-GCD(int a, int b) {  

   if (b == 0) return a; else return RECURSIVE-GCD(b, a % b);  

}  

定理2:(フランスの数学者ラメによって証明された)ユークリッドアルゴリズムに必要な除算回数はmとnの中の小さいその数の10進数の5倍を超えない
定理3:(やや弱点)......2 log(n+1)を超えず、そのうちnは小さい数である
 
拡張ユークリッドアルゴリズム
拡張ユークリッドアルゴリズムは,ax+by=Gcd(a,b)=d(解が必ず存在し,数論における相関定理に基づいて)になるように,既知のa,bのxのセットを解くために用いられる.
x,yの方法の理解を解く
a>bとする.1,明らかにb=0,gcd(a,b)=aである.このときx=1,y=0;  　　2,ab!=0の場合ax 1+by 1=gcd(a,b)とする.  　　bx2+(a mod b)y2=gcd(b,a mod b);素朴なユークリッド原理によればgcd(a,b)=gcd(b,a mod b);則:ax 1+by 1=bx 2+(a mod b)y 2;すなわち、ax 1+by 1=bx 2+(a-(a/b)*b)y 2=ay 2+bx 2-(a/b)*by 2;恒等定理に基づいて得られる:x 1=y 2;y1=x2-(a/b)*y2;x 1,y 1を解く方法:x 1,y 1の値はx 2,y 2に基づいている.以上の考え方は再帰的に定義されているが,gcdの絶えずの再帰的な解は必ずb=0になるので,再帰は終了することができる.
拡張ユークリッドアルゴリズムを用いて不定方程式を解決する方法
不定整数方程式pa+qb=cの場合、c mod Gcd(a,b)=0の場合、その方程式には整数解が存在し、そうでなければ整数解は存在しない.以上、p*a+q*b=Gcd(a,b)の解p 0,q 0のセットを見つけた後、/*p*a+q*b=Gcd(a,b)の他の整数解は、p=p 0+b/Gcd(a,b)*t q=q 0-a/Gcd(a,b)*t(tは任意の整数)pa+qb=cの整数解について、p*a+q*b=Gcd(a,b)の各解にc/Gcd(a,b)を乗じるだけで、p*a+q*b=Gcd(a,b)の解p 0,q 0のセットが見つかった後、p*a+q*b=cの解p 1=p 0*(c/Gcd(a,b)),q 1=q 0*(c/Gcd(a,b))のセットが得られるはずです.p*a+q*b=cの他の整数解は、p=p 1+b/Gcd(a,b)*t q=q 1−a/Gcd(a,b)*t(ここでtは任意の整数)p、qはp*a+q*b=cのすべての整数解を満たす.プログラミング時にexgcdは「中国余数定理」に関する知識を解くために多く使われています.例えば、nを5余2で割って13余3で割ると、nが最小でいくらになりますか.すべてのnはどんな条件を満たしていますか.　　n(min)=42 　　n=42+k*65
 
 
中国の残りの定理:
総数をn,型aをx,型bをy,型cをzとし,x,y,zが既知であれば最小のnを求める.
n=(x*a 1+y*b 1+z*c 1)%d;
ここで、a 1=y*zの倍数におけるモードaは1の最小数に等しい.
b 1=x*zの倍数におけるモードbは1の最小の数に等しい.
c 1=x*yの倍数におけるモードcは1の最小の数に等しい.
d=a,b,cの最小公倍数.
中国の残りの定理原版の韓信点兵版:
韓信が点兵した時に発明したアルゴリズムだという.兵士総数をn,型3得x,型5得y,型7得zとし,x,y,zが既知であれば最小のnを求める.
n=(x*70+y*21+z*15)%105;
次の詩で記憶を助けることができます.
3人で70人の旅をする.70は35(5)×7)の倍数における型3が1に等しい最小の数.
五樹梅二十一枝21は21(3)×7)の倍数における型5が1の最小数に等しい.
七子団欒の月はちょうど半分である.15は15(3)×5)の倍数における型7が1の最小の数に等しい.
百五を除いて得られる.105は3,5,7の最小公倍数である.
 
3,5,7でなければ同じ方法で解く.
 
最後に私の個人サイトへようこそ:1024 s