最終更新:2019/04/14

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

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

不定方程式とは,$3x+5y=2$ のように,方程式の数よりも未知変数の数が多いような方程式のことです。

この記事では,$ax+by=c$ という不定方程式の整数解について,重要な定理の証明と,実際に不定方程式の一般解を求める方法を説明します。

不定方程式の例

$2x+4y=1$ という不定方程式を満たす整数 $(x,y)$ は存在するでしょうか?
$(x,y)$ が整数のとき,$2x+4y$ は偶数なので,$2x+4y=1$ になることはありません。よって,この不定方程式に整数解は存在しません。

$3x+5y=2$ という不定方程式を満たす整数 $(x,y)$ は存在するでしょうか?
実は,$m$ を整数として,$(x,y)=(4+5m,-2-3m)$ とすると,$(x,y)$ は解になります。

このように,$ax+by=c$ という不定方程式は,整数解を持たない場合と,無数の整数解を持つ場合があります。

不定方程式の整数解についての定理

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

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

例えば,$2x+4y=1$ という不定方程式については,$1$ はgcd$(2,4)=2$ の倍数ではないので,整数解を持たないことが分かります。

また,$3x+5y=2$ という不定方程式については,$2$ はgcd$(3,5)=1$ の倍数なので,整数解を持つことが分かります。

特に,定理1で $c=1$ とした,以下の定理2が重要です。

定理2:
$ax+by=1$ が整数解を持つ
$\iff$ $a$ と $b$ は互いに素

定理2の証明

まず「 $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$ は互いに素なのでこれは矛盾。

定理1の証明

$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$ は整数解を持つ。

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

一次不定方程式の解き方

不定方程式 $ax+by=1$ に解が存在する場合に,その一般解を求める問題が頻出です。

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

具体例で説明します。

$3x+5y=2$ の整数解を求めてみる。

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)$

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

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

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

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