拡張ユークリッド互除法について

　蟻本を見ていると、以下のような文章がでてくる。

「(省略) これは、a * x + b * y = 1 となる(x, y)を求める問題に他ならない。この式から明らかなようにgcd (a, b) != 1のときは、整数解(x, y)は存在しません。」

　自分にとっては明らかじゃなかったので、ちょっと考えてみた。

gcd(a, b) != 1のとき、上記の条件を満たす(x, y)が存在しないことを背理法で示す。

gcd(a, b) = d, d > 1とすると、

a * x + b * y = 0 (mod d)

である。

しかし、

1 != 0 (mod d)

であるため、矛盾。よって、gcd(a, b) != 1のときは上記の条件を満たす(x, y)は存在しない。□

あら、確かに。自明レベルの内容だった。。

　逆に、gcd(a, b) = 1 のときは、上記の条件を満たす(x, y)が必ず存在することを証明してみる。

a * x + b * y = 1より

x = (1 - b * y) / a となる(x, y)を求めればよい。

つまり、1- b * y = 0 (mod a)となる任意の整数yが存在すればよいことになる。

移行すると、

b* y = 1 (mod a)

となるが、gdc(a, b) = 1 からaとbがrelatively primeなので、bの逆元yは存在する。

よって、gcd(a, b) = 1のときは、解(x, y)が存在する。□

ふむふむ。なるほど。。

　証明が出来てもプログラムが書けないことには意味がない。ということで書いてみる。

int extGcd(int a, int b, int &x, int &y) {
int d = a;

if (b) {
  d = extGcd(b, a%b, y, x);
  y -= a / b * x;
} else {
  x = 1;
  y = 0;
}

return d;
}

蟻本では、b == 0のとき、y = 0としているが、ここは任意の整数でいい。（逆元は一つだけじゃないので。）たとえば、(a, b) = (11, 13)として、a*x + b * y = 1となる(x, y)を複数個求めてみる。

ちょっとだけ、extGcd()を書きかえて、b=0のときのyの値を選べるようにしてやる。（本当は、クロージャみたいなので書くといいのかも。Haskellでやればよかったかな・・）

int extGcd(int a, int b, int y0, int &x, int &y) {
 int d = a;

 if (b) {
   d = extGcd(b, a%b, y0, y, x);
   y -= a / b * x;
 } else {
   x = 1;
   y = y0;
 }

 return d;
}

int main () {
 int x, y;
 int a = 11;
 int b = 13;

 for (int i = 0; i < 10; i++) {
   int d = extGcd(a, b, i, x, y);
   printf("%d * %d + %d * %d = %d\n", a, x, b, y, (a*x+b*y));
 }
 return 0;
}

で、(x, y)の組が10個求まりました。