一次不定方程式ax+by=cの整数解

$(x,y)$ が整数のとき，$2x+4y$ は偶数になる。

よって，$2x+4y=1$ になることはない。よって，この不定方程式に整数解は存在しない。

実は，$m$ を整数として，

$(x,y)=(4+5m,-2-3m)$

とすると，$(x,y)$ は解になる。実際，

$3(4+5m)+5(-2-3m)=2$

となる。なお，上記の解の見つけ方は記事の後半で説明する。

$\Rightarrow$ の対偶を証明します。

$a$ と $b$ が互いに素でないとき，$a$ と $b$ の公約数の1つを $d\geq 2$ とおくと $ax+by$ は $d$ の倍数となり解を持たない。

$\Leftarrow$ を証明します。

$a$ と $b$ が互いに素なとき $a,2a,3a,\cdots,(b-1)a$ を $b$ で割った余りは全て異なる（※）ので，余りが1となるようなものが存在する。

それを $ma$ とおき，$b$ で割った商を $n$ とおくと，

$ma=bn+1$

つまり，$am-bn=1$ となり $(m,-n)$ は整数解になっている。

$\Rightarrow$を証明します。

$a,b$ は $\mathrm{gcd}(a,b)$ の倍数なので整数解 $m,n$ に対して $am+bn$ も $\mathrm{gcd}(a,b)$ の倍数。つまり $c$ は $\mathrm{gcd}(a,b)$ の倍数。

$\Leftarrow$ を証明します。

$a=p\cdot\mathrm{gcd}(a,b)$ , $b=q\cdot\mathrm{gcd}(a,b)$ とおける（ただし $p,q$ は互いに素）。

さきほどの結果から $pm+qn=1$ は整数解を持つので両辺を $\mathrm{gcd}(a,b)$ 倍して，

$am+bn=\mathrm{gcd}(a,b)$

も整数解を持つことが分かる。

よって，$c$ が $\mathrm{gcd}(a,b)$ の倍数のとき，両辺を適当に整数倍すれば右辺が $c$ となるので $ax+by=c$ は整数解を持つ。

1. まず整数解を1つ求める。

直感で求めても良い。難しい場合は，定理2の証明中の方法を使う。つまり，$a=3$ の倍数 $3,6,9,12$ の中で $b=5$ で割って $2$ 余るものを見つけると $12$ が当たり。よって，割り算の式を書くと

$3\cdot 4=5\cdot 2+2$

となり，$(4,-2)$ が $3x+5y=2$ の整数解になっていることが分かる。

2. もとの方程式と引き算する。

見つけた解： $3\cdot 4+5\cdot (-2)=2$

と元の方程式を辺々引き算して

$3(x-4)+5(y+2)=0$

を得る。

3. 一般解を求める

$3$ と $5$ が互いに素なので，

$x-4=5m$ とおける。このとき $y+2=-3m$ となる。

つまり，一般解は $(x,y)=(4+5m,-2-3m)$