拡張ユークリッド互除法で得られる解の大きさについて

Question

拡張ユークリッド互除法で gcd(a,b) および ax+by=gcd(a,b) の整数解 (x0,y0) を得るコードを書いているのですが、x0 および y0 の大きさを数学的に評価する方法が知りたいです。

コードのverifyのために Aizu Online Judge (AOJ) の NTL_1_E 問題 を利用しているのですが、この問題では整数解について以下の条件が課されています:

「|x|+|y| が最小のものを出力する。最小のものが複数ある場合はその中で x ≤ y であるものを出力する。」

質問は以下の通りです:

• 拡張ユークリッド互除法は常に上記条件を満たす解を与えるのか?
• もしそうならば、それはどのように証明するのか?
• 私のコードは上記条件を常に満たすか?

私のコードは以下の通りです(一応AOJ上では正解と判定されましたが、テストケースに負数や0が含まれていないこともあり、本当に上記の条件が満たされているのか確信が持てません)

/**
 * 蟻本のコードを負の引数も正しく処理できるようにしたもの
 */

#include <bits/stdc++.h>

using namespace std;

int sgn(int x) {
    if(x > 0)
        return 1;
    else if(x < 0)
        return -1;
    else
        return 0;
}

int extgcd_impl(int a, int b, int& x, int& y) {
    int d = a;
    if(b != 0) {
        d = extgcd_impl(b, a%b, y, x);
        y -= (a/b) * x;
    }
    else {
        x = 1; y = 0;
    }
    return d;
}

int extgcd(int a, int b, int& x, int& y) {
    int d = extgcd_impl(abs(a), abs(b), x, y);
    x *= sgn(a);
    y *= sgn(b);
    return d;
}

int main() {
    int a, b;
    cin >> a >> b;

    int x, y;
    int g = extgcd(a, b, x, y);

    //cout << g << "\n";
    cout << x << " " << y << "\n";

    return 0;
}

AOJ submission

---

2019/02/25 追記:

StackExchange の記事 を参考にしつつ証明を考えてみました。あまりこういうのは書いたことがないので、間違っていたらご指摘いただきたいです。正しいという確信が得られるまでもうしばらく回答を受け付けたいと思います。

2019/02/27 追記: 〆切ました。

extgcd が問題の条件を満たす解を与えることの証明

※gcd(0,0)=0 と定義する。

a,b を整数とする。g=gcd(a,b) および ax+by=g の整数解 (X,Y) を求める関数 extgcd(a,b)=(g,X,Y) を考える。
|X|+|Y| が最小の解を最小解と呼ぶ(唯一とは限らない)。

• extgcd(a,b)=(g,X,Y) ならば extgcd(-a,b)=(g,-X,Y), extgcd(a,-b)=(g,X,-Y) なので、a>=0, b>=0についてのみ考えれば十分。
• gcd(a,b)>1 のとき、a=ga', b=gb' とおくと、ax+by=g は a'x+b'y=1 に帰着する。よって、gcd(a,b)<=1 についてのみ考えれば十分。
• extgcd(a,b)=(g,X,Y) ならば extgcd(b,a)=(g,Y,X) なので、a>=b についてのみ考えれば十分。
• extgcd(0,0)=(0,0,0), extgcd(1,0)=(1,1,0), extgcd(1,1)=(1,0,1) と定義する。いずれも最小解になっている。

以上より、後は gcd(a,b)=1, a>b>=2 についてのみ考えれば十分。
extgcd(a,b)=(1,X,Y) とする。a を b で割って a=qb+r と表す (0<r<b)
extgcd(b,r)=(1,X',Y') ならば、bX'+rY'=1 に r=a-qb を代入して
X=Y', Y=X'-qY' が得られる。

このとき、|X|<=b/2, |Y|<=a/2 が成り立つことを帰納法で示す。

g=gcd(a,b)=1 だから、extgcdの再帰呼び出し中のある時点で第2引数が1になる。この直前の extgcd(A,B) を考える。
A=QB+1, A>B>=2 である。
extgcd(B,1)=(1,0,1) より、extgcd(A,B)=(1,1,-Q) である。よって
|1|<=B/2, |-Q|=Q<=QB/2<A/2 より、A,B については命題は成り立っている。

次に一般の a,b について考える。a=qb+r, extgcd(a,b)=(1,X,Y) とする。
extgcd(b,r)=(1,X',Y'), |X'|<=r/2, |Y'|<=b/2 ならば、
|X|=|Y'|<=b/2
|Y|=|X'-qY'|<=|X'|+|qY'|<=r/2+qb/2=(qb+r)/2=a/2
より、a,b についても命題は成り立つ。

よって命題は gcd(a,b)=1, a>b>=2 なる全ての a,b について成り立つ。

ところで、ax+by=1 の一般解は (x,y)=(X+mb,Y-ma) と表せる。
|X|<=b/2 より、m!=0 のとき |X+mb|>=|X|
|Y|<=a/2 より、m!=0 のとき |Y-ma|>=|Y|
なので、X,Y は最小解である。最小解が他に存在するためには |X|=b/2, |Y|=a/2 でなければならず、このとき aX+bY は ab, 0, -ab のいずれかになるが、いずれも gcd(a,b)=1 に反する。よって、gcd(a,b)=1, a>b>=2 のとき、ax+by=1 の最小解は唯一である。

他に最小解が複数存在しうるのは (a,b)=(1,1) のみであり、このとき ax+by=1 の最小解は (1,0),(0,1) の2通りある。しかし extgcd(1,1)=(1,0,1) と定義したから、X<=Y は満たされている。

結局、この extgcd の定義では常に最小解が得られ、最小解が複数ある場合は X<=Y なるものが得られる。証明終

Answer 1

厳密な証明ができるわけではありませんが、おそらく最初の質問

拡張ユークリッド互除法は常に上記条件を満たす解を与えるのか?

は「YES」だと思います。
ユークリッド互除法のやり方は、ざっくりいえば数をブロックのようなものでイメージして、「片方のブロックに、もう片方のブロックが何個分入るか」というのを繰り返していくものです。最大公約数まで求まった時点で、それは「最大公約数に至るまでに必要な最低限のブロック」を敷き詰めることになるので、その個数である特殊解は絶対値最小のものになると思います。

Comments

[vabuff]

考えてみたのですが、「特殊解はブロックの個数である」という言葉の内容がよく理解できませんでした。
例えば extgcd(13,8) の場合はどのように解釈すればよいでしょうか?
質問中のコードでは extgcd(13,8) は g=1, x=-3, y=5 を返しますが、「負の個数とは何だろう?」というところで行き詰まってしまいました。

[swordone]

もとの方程式が13x+8y=1だと思うのですが、これを
8y-13(-x)=1と見れば、
8のブロック5個(40)と13のブロック3個(39)との差が1である、ということです。

[vabuff]

ありがとうございます。
「最大公約数まで求まった時点で、それは「最大公約数に至るまでに必要な最低限のブロック」を敷き詰めることになる」という部分ですが、なぜ最低限の個数になるのかがよくわからず考え中です。

蟻本を読み直したところ
extgcd(a,b)の返り値を(g,X,Y) (g=gcd(a,b)) としたとき、ab>0 であれば |X|<=b, |Y|<=a であることは証明できたのですが、これから直ちに「|X|+|Y| が最小で、最小のものが複数ある場合 X<=Y」となることは言えない気がします。
頑張れば |X|, |Y| の上限をもう少し抑えられそうなので試行錯誤中ですが、こんなにゴチャゴチャ考えなくても問題の条件を満たすことはわかるものなのでしょうか?

[vabuff]

自分なりに証明を考えてみたので質問本文に追記しました。これで条件を満たすことを示せているでしょうか?
証明するにしてももっと簡単な方法がありそうな気もするのですが…

[vabuff]

一応納得できたと思うので締め切りました。ありがとうございました。