ユークリッドアルゴリズムの拡張‐不定方程式の解

拡張ユークリッドアルゴリズムは,p*a+q*b=Gcd(p,q)(解が必ず存在し,数論における相関定理に基づいて)になるように,既知のa,bの一連のpを解くために用いられる.拡張ユークリッドはモード線形方程式と方程式群を解くのによく用いられる.以下はC++を用いた実装である: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;}この実装をGcdの再帰実装と比較すると,次のx,y賦値過程が多く発見され,これが拡張ユークリッドアルゴリズムの真髄である.a'=b,b'=a%bに対してxを求め,yはa'x+b'y=Gcd(a',b')をb'=a%b=a-a/b*b(注:ここでは/プログラム設計言語での除算)により得ることができる:a'x+b'y=Gcd(a',b')=>bx+(a-a/b*b)y=Gcd(a',b')=Gcd(a,b)=>ay+b(x-a/b*y)=Gcd(a,b)であるため、aおよびbに対して、彼らの対応するp,bqはそれぞれyと(x-a/b*y)補足:拡張ユークリッドアルゴリズムを用いて不定方程式を解決する方法について不定整数方程式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)を乗乗乗乗せればよい整数解を探す方法が既にリストされている.を選択します.

 :

                         ，               。           a*x+b*y=m，          ，     gcd(a,b) | m， a，b          m(m%gcd(a,b)==0)。     ，  a%gcd(a,b)==b%gcd(a,b)==0，  a*x+b*y      gcd(a,b)，        ，      m  a*x+b*y，         ，                        。



         a*x+b*y=m            ，     x y ？



      1. a1=a/gcd(a,b)，b1=b/gcd(a,b)，m1=m/gcd(a,b)。            a*x1+b*y1=gcd(a,b)     x1 y1，  x=x1*m1,y=y1*m1       。       gcd(a,b)=gcd(b,a%b)，  a*x1+b*y1=gcd(a,b)=gcd(b,a%b)=b*x2+(a%b)*y2，                              。 k=a/b( )，r=a%b(  )，  a=k*b+r。  r=a-k*b，    ，  a*x1+b*y1=b*x2+(a-(a/b)*b)y2=a*y2+b*(x2-(a/b)*y2) => x1=y2，y1=x2-(a/b)*y2。                            ，     x，y   。                           ，             a b         ，      a*x1+b*y1=gcd(a,b)   x1 y1      。                        。



__int64 exGcd(__int64 a,__int64 b,__int64 &x,__int64 &y){

    if(b==0){

        x=1;

        y=0;

        return a;

    }

    __int64 g=exGcd(b,a%b,x,y);

    __int64 temp=x;

    x=y;

    y=temp-(a/b)*y;

    return g;

}



     2.  x，y      x1*m1，y1*m1，              ，              x  y       。  x  ，       ？       ，   x，y    a*x+b*y=m，  a*(x+n*b)+b*(y-n*a)=m       。    x+n*b(n=…，-2，-1，0，1，2，…)       x    ，     x      y    ，     x        y   。 k  x+k*b>0，x          (x+k*b)%b，            ？？               gcd(a,b)，     a1*x+b1*y=m1，        ，         (x+k*b1)%b1，  b1<=b，                。              while(x<0)x+=b1          ，         ，   b1  b(b b1   )，  b          x 。