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

ユークリッドアルゴリズム
ユークリッドアルゴリズムは、2つの整数a,bの最大公約数を計算するために、転がり相除去法とも呼ばれる.
基本アルゴリズム:a=qb+rとし、a,b,q,rが整数である場合、gcd(a,b)=gcd(b,r)、すなわちgcd(a,b)=gcd(b,a%b)とする.
1つ目の証明:
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)の公約数は同じであり,その最大公約数も必然的に等しいことが証明された.
 
2つ目の証明:
ユークリッドアルゴリズムが成立したことを証明するには、gcd(a,b)=gcd(b,r)であり、gcdは最大公約数をとるという意味であり、r=a mod bの下にgcd(a,b)=gcd(b,r)はcをa,bの最大公約数、すなわちc=gcd(a,b)とすると、a=mc,b=ncがあり、ここでm,nは正の整数であり、m,nは互いに質量数であることがr=a mod bから分かる.r=a-qbのうち、qが正の整数であれば、r=a-qb=mc-qnc=(m-qn)cb=nc、r=(m-qn)c、n、(m-qn)互質(n,m-qnが互質しないと仮定すると、n=xd、m-qn=ydであり、x,y,dはいずれも正の整数であり、d>1ではa=mc=(qx+y)dc、b=xdcである.bの最大公約数はdcとなり,前提と矛盾するため,n,m−qnは一定の相互質)でgcd(b,r)=c=gcd(a,b)が得られる.
 
アルゴリズムの実装:
最も簡単な方法は再帰アルゴリズムを適用することであり、コードは以下の通りである.

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return 
        gcd(b,a%b);
}

コードは次のように最適化されます.

int gcd(int a,int b)
{
     return b ? gcd(b,a%b) : a;
}

もちろん反復形式も使用できます.

int Gcd(int a, int b)
{
    while(b != 0)
    {
    　　int r = b;
    　　b = a % b;
    　　a = r;
    }
    return a;
}

拡張ユークリッドアルゴリズム
基本アルゴリズム:完全に0ではない非負の整数a,b,gcd(a,b)はa,bの最大公約数を表し、必然的に整数対x,yが存在し、gcd(a,b)=ax+byとなる.
証明: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になるので,再帰は終了することができる.
 
拡張ユークリッドの再帰コード:

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

拡張ユークリッド非再帰コード:

<span style="background-color: rgb(255, 255, 255);">int exgcd(int m,int n,int &x,int &y)
{
    int x1,y1,x0,y0;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=m%n;
    int q=(m-r)/n;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        m=n; n=r; r=m%n;
        q=(m-r)/n;
    }
    return n;
}</span>

拡張ユークリッドアルゴリズムの応用は主に以下の3つの方面がある.
(1)不定方程式を解く;
(2)モード線形方程式(線形同余方程式)を解く.
(3)型の逆元を解く.
 
(1)拡張ユークリッドアルゴリズムを用いて不定方程式を解決する方法:
不定整数方程式pa+qb=cの場合、c mod Gcd(p,q)=0の場合、その方程式には整数解が存在し、そうでなければ整数解は存在しない.p*a+q*b=Gcd(p,q)の一連の解p 0,q 0を見つけた後、p*a+q*b=Gcd(p,q)の他の整数解は、p=p 0+b/Gcd(p,q)*tq=q 0-a/Gcd(p,q)*t q=q 0-a/Gcd(p,q)*t(ここでtは任意の整数)pa+ qb=cの整数解について、p*a+a+q b=Gcd(p,q)の各解にc/Gcd(p,q)を乗乗せればよい.
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 = p1 + b/Gcd(a, b) * t
q=q 1-a/Gcd(a,b)*t(ここでtは任意の整数)
p,qはp*a+q*b=cのすべての整数解である.
関連証明書を参照してください.http://www.cnblogs.com/void/archive/2011/04/18/2020357.html
 
拡張ユークリッドアルゴリズムを用いて不定方程式ax+by=cを解く.
コードは次のとおりです.

<span style="background-color: rgb(255, 255, 255);">bool linear_equation(int a,int b,int c,int &x,int &y)
{
    int d=exgcd(a,b,x,y);
    if(c%d)
        return false;
    int k=c/d;
    x*=k; y*=k;    //          
    return true;
}</span>

(2)拡張ユークリッドアルゴリズムを用いてモード線形方程式を解く方法:
同余方程式ax≡b(mod n)は未知数xに対して解があり、gcd(a,n)|bのみである.方程式に解がある場合,方程式にはgcd(a,n)個の解がある.
解方程式ax≡b(mod n)は解方程式ax+ny=bに相当し,(x,yは整数)
d=gcd(a,n)とし,整数xとyの場合,d=ax+ny(拡張ユークリッドで導出)を満たす.d|bの場合、方程式
a*x 0+n*y 0=d,方程式の両側にb/dを乗じ,(d|bのため整除可能),a*x 0*b/d+n*y 0*b/d=bを得た.従ってx＝x 0*b／d,y＝y 0*b／dはax＋ny＝bの解であり,x＝x 0*b／dはax＝b(mod n)の解である.
ax≡b(mod n)の1つの解はx 0=x*(b/d)mod nであり、方程式のdつの解はそれぞれxi=(x 0+i*(n/d))mod n{i=0...d−1}である.
ans=x*(b/d)、s=n/dとする.
方程式ax≡b(mod n)の最小整数解は,(ans%s+s)%s;
関連証明:
方程式にはx 0=x′(b/d)mod nという解があることを証明した.a*x 0=a*x'(b/d)(mod n)a*x 0=d(b/d)(mod n)(ax'=d(mod n)=b(mod n)
証明方程式にはd個の解がある:xi=x 0+i*(n/d)(mod n);a*xi(mod n)=a*(x 0+i*(n/d)=(a*x 0+a*i*(n/d))=a*x 0(mod n)=a*x 0(mod n)=b
     
まず簡単な例を見てみましょう
5x=4(mod3)
解得x=2,5,8,11,14......
これにより,解の間隔が3であるという法則が見いだされる.
では、この解の間隔はどのように決まるのでしょうか.
第1の解を見つけることができ、解間の間隔を求めることができれば、モードの線形方程式の解集を求めることができる.
解の間隔をdxとする.
そんなに
a*x = b(mod n);
a*(x+dx) = b(mod n);
2つの式が減算され、次のようになります.
a*dx(mod n)= 0;
すなわちa*dxはaの倍数であるとともにnの倍数である、すなわちa*dxはaとnの公倍数である.dxを求めるためには、aとnの最小公倍数を求めるべきであり、このとき対応するdxは最小である.
aとnの最大公約数をdとすると、aとnの最小公倍数は(a*n)/dとなる.
すなわちa*dx=a*n/d;
だからdx=n/d.
そこで解の間の間隔を求める.
コードは次のとおりです.

<span style="background-color: rgb(255, 255, 255);">bool modular_linear_equation(int a,int b,int n)
{
    int x,y,x0,i;
    int d=exgcd(a,n,x,y);
    if(b%d)
        return false;
    x0=x*(b/d)%n;   //  
    for(i=1;i<d;i++)
        printf("%d
",(x0+i*(n/d))%n);
    return true;
}</span>

(3)ユークリッドアルゴリズムでモデルを求める逆元:
同余方程式ax≡b(mod n),gcd(a,n)==1の場合,方程式は一意解のみであった.
この場合,b==1の場合,同余方程式はax=1(mod n),gcd(a,n)=1である.
このとき求めたxをaの対モードn乗算の逆元と呼ぶ.
同余方程式ax=1(mod n),gcd(a,n)=1の解が解方程式である
ax+ny=1,x,yは整数である.これは拡張ユークリッドアルゴリズムで求めることができ,元の同余方程式の唯一の解は拡張ユークリッドアルゴリズムで得られたxである.