一次不定方程

これは最大公約数が単に「共通の最大の因数」であるだけでなく、実際に $a$ と $b$ の整数結合として到達可能であることを示す——これが $ax+by=c$ の可解性判定を成り立たせる鍵となる事実である。

$a$ と $b$ の正の整数結合全体からなる集合 $S=\{au+bv : u,v\in\mathbb{Z}\}\cap\mathbb{Z}_{>0}$ を考える。$a,b$ はどちらも $0$ ではないので $S$ は空でなく($|a|$ または $|b|$ を含む)、整列原理により $S$ には最小元 $d=au_0+bv_0>0$ が存在する。

$d\mid a$ を示す:$a=qd+r$($0\le r<d$)と割る。すると $r=a-qd=a-q(au_0+bv_0)=a(1-qu_0)+b(-qv_0)$ はそれ自体 $a,b$ の整数結合である。もし $r>0$ なら $r$ は $S$ に属し $d$ より小さくなり最小性に矛盾する。よって $r=0$、すなわち $d\mid a$ である。$a$ の代わりに $b$ で同じ議論をすれば $d\mid b$ も分かる。

$d$ は $a$ と $b$ の公約数なので $d\le \gcd(a,b)$ である。逆に、$a$ と $b$ の任意の公約数 $e$ は $au_0+bv_0=d$ を割り切るので $e\le d$。$e=\gcd(a,b)$ とすれば $\gcd(a,b)\le d$ を得る。

両方の不等式を合わせると $d=\gcd(a,b)$ であり、構成より $d=au_0+bv_0$ である。これはまさに $u=u_0,v=v_0$ とするベズーの等式である。

これは問題を完全に解決する:一つの整除チェックで可解性が決まり、一つでも解が見つかれば $t$ による一パラメータ族が他のすべての解を与える——推測は不要である。

($\Rightarrow$)$(x,y)$ が整数解ならば $d=\gcd(a,b)$ は $ax$ と $by$ の両方を割り切るので $ax+by=c$ を割り切る。よって $d \mid c$ は必要条件である。

($\Leftarrow$)$d \mid c$ とし、$c=de$ と書く。ベズーの等式より $au_0+bv_0=d$ を満たす $u_0,v_0$ が存在する。$e$ 倍すると $a(u_0e)+b(v_0e)=de=c$ となり、$(x_0,y_0)=(u_0e,\,v_0e)$ が整数解である。これで可解性が示された。

次に解 $(x_0,y_0)$ を一つ固定し、$(x,y)$ を他の任意の解とする。$ax+by=c$ から $ax_0+by_0=c$ を引くと $a(x-x_0)+b(y-y_0)=0$、すなわち $a(x-x_0)=-b(y-y_0)$ を得る。両辺を $d$ で割ると $\frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0)$ であり、$\gcd(a/d,\,b/d)=1$ なので因子 $\frac{b}{d}$ は $x-x_0$ を割り切らねばならない(互いに素性の標準的帰結:$p\mid mn$ かつ $\gcd(p,m)=1$ なら $p\mid n$)。よって $x-x_0=\frac{b}{d}t$ となる整数 $t$ が存在し、代入すると $y-y_0=-\frac{a}{d}t$ を得る。

逆に、任意の整数 $t$ に対し $x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$ を $ax+by$ に代入すると $ax_0+by_0+t\left(\frac{ab}{d}-\frac{ab}{d}\right)=c+0=c$ となり、そのような組がすべて解であることが確かめられる。したがって解の集合はちょうど $x=x_0+\dfrac{b}{d}t,\ \ y=y_0-\dfrac{a}{d}t\ \ (t\in\mathbb{Z})$ である。