Page List

Search on the blog

2011年7月29日金曜日

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

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

「(省略) これは、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個求まりました。

1 件のコメント: