可解性と一般解

($\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})$ である。