2014/04/21

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

分野: 整数問題  レベル: 入試対策

$x,y$ に関する二元一次不定方程式 $ax+by=c$ が整数解を持つ
$\iff$ $c$ はgcd$ (a,b)$ の倍数
特に, $ax+by=1$ が整数解を持つ
$\iff$ $a$ と $b$ は互いに素

gcd$ (a,b)$ は $a$ と $b$ の最大公約数を表します。

一次不定方程式 $ax+by=c$ には「ベズー等式(Bezout’s identity)」という立派な名前がついています。

一次不定方程式に関する問題は超頻出です。
このページでは上記の公式の証明と,実際に不定方程式の一般解を求める方法を説明します。

$ax+by=1$ についての証明

まず「 $ax+by=1$ が整数解を持つ $\iff$ $a$ と $b$ が互いに素」を証明します。

方針:$\Rightarrow$ は対偶を取れば簡単です。$\Leftarrow$ の証明は非常に有名なテクニックを使うのでまるごと覚えておくとよいでしょう。

$\Rightarrow$ の対偶の証明

$a$ と $b$ の公約数を $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)$ は整数解になっている。

※の証明(背理法)
$ia$ と $ja\:(i>j)$ を $b$ で割った余りが同じだと仮定すると,$(i-j)a$ は $b$ の倍数となるはずだが,$1\leq i-j <b$ かつ $a$ と $b$ は互いに素なのでこれは矛盾。

ベズーの等式:$ax+by=c$ についての証明

$ax+by=c$ が整数解を持つ $\iff$ $c$ はgcd$ (a,b)$ の倍数,を証明します。

方針:$\Rightarrow$は先ほどと同様に簡単です。$\Leftarrow$ も先ほどの結果からすぐに分かります。

$\Rightarrow$ の証明

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

$\Leftarrow$ の証明

$a=p\cdot $gcd$ (a,b)$, $b=q\cdot $gcd$ (a,b)$ とおける。(ただし $p,q$ は互いに素。)
先ほどの結果から $pm+qn=1$ は整数解を持つので両辺をgcd$ (a,b)$ 倍して,
$am+bn= $gcd$ (a,b)$ も整数解を持つことが分かる。
よって,$c$ がgcd$ (a,b)$ の倍数のとき,両辺を適当に整数倍すれば右辺が $c$ となるので $ax+by=c$ は整数解を持つ。

なお,ユークリッドの互除法を用いた構成的な証明方法もあります。
→ユークリッドの互除法の証明と不定方程式

一次不定方程式の解き方

不定方程式に解が存在する場合にその一般解を求める問題が頻出です。

一次不定方程式の解き方:
1:上記証明中の方法またはユークリッドの互除法または直感で解を1つ求める。
2:もとの方程式と引き算して $a(x-x_0)+b(y-y_0)=0$ の形にする。
3:一般解を求める

具体例で説明します。

$3x+5y=2$
$3,6,9,12$ の中で $5$ で割って $2$ 余るものを見つけると $12$ が当たり。
よって,$3\cdot 4=5\cdot 2+2$ となり,$(4,-2)$ が1つの解になっている。
よって,元の方程式と辺々引き算して
$3(x-4)+5(y+2)=0$ が成立する。
$3$ と $5$ が互いに素なので,
$x-4=5m$ とおける。このとき $y+2=-3m$ となり,
一般解は$(x,y)=(4+5m,-2-3m)$

数字が非常に大きい問題は入試では出ないと思いますが,その場合は1つの解をユークリッドの互除法を用いて求めた方が早いです。どちらの方法も使えるようになっておきましょう。

特殊解と同次方程式の一般解の和で表すのは大学に入ってからもよく出てくる形です

Tag: 不定方程式の解き方まとめ
Tag: 素数にまつわる覚えておくべき性質まとめ
Tag: 数学Aの教科書に載っている公式の解説一覧

分野: 整数問題  レベル: 入試対策