一次不定方程式 ax + by = c | 初等整数論

方程式の解を求めるとき、未知数がどの範囲の数を表すかによって、答えは変わります。たとえば、 $7x+11y=100$ を満たす実数の組は直線上に並びますが、そのうち整数の組を求めるには、係数の整除関係を考える必要があります。

整数解を一つ見つけても、ほかの整数解があるか、あるならどのような形で表されるかは、まだ明らかではありません。整数 $a,b,c$ に対して、 $ax+by=c$ の整数解を求める方程式を一次不定方程式といいます。一次不定方程式は、整除や最大公約数の性質を、方程式の解の存在と構造に結びつける基本的な対象です。

本記事では、一次不定方程式の整数解について、基本的な性質と代表的な例を解説します。

1 一次不定方程式とベズーの等式

整数 $a,b,c$ に対し、 $ax+by=c$ を満たす整数の組 $(x,y)$ を求める方程式を、一次不定方程式といいます。解を一つ固定したとき、その解を特殊解と呼びます。

補題 1.1. $a,b$ を少なくとも一方が $0$ でない整数とし、 $d=\gcd(a,b)$ とする。整数 $r,s$ が存在して $ar+bs=d$ が成り立つ。この等式をベズーの等式という。

証明. $a=0$ なら $r=0$ , $s=b/|b|$ とし、 $b=0$ なら $r=a/|a|$ , $s=0$ とすると、 $ar+bs=d$ となる。 $a,b$ がともに $0$ でない場合、 $|a|,|b|$ に互除法を適用する。§A4.1 定理 3.3により、互除法は有限回で停止し、最後の除法で割る数は $d$ である。最初の二数 $|a|=(a/|a|)a$ , $|b|=(b/|b|)b$ は、 $a,b$ の整数係数の和である。各段の余りは、直前の二数の一方から他方の整数倍を引いたものなので、余りも $a,b$ の整数係数の和である。したがって最後の除法で割る数 $d$ も整数係数の和となり、 $ar+bs=d$ を満たす整数 $r,s$ が得られる。▨

2 整数解の存在と一般解

定理 2.1. $a,b,c$ を整数とし、 $a,b$ の少なくとも一方が $0$ でないとする。 $d=\gcd(a,b)$ とおく。 $ax+by=c$ が整数解をもつための必要十分条件は、 $d$ が $c$ を割り切ることである。整数解 $(x_0,y_0)$ が一つ存在するとき、すべての整数解は

x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t\qquad(t\in\Z)

で表され、各解に対応する整数 $t$ はただ一つに定まる。

証明. 整数解 $(x,y)$ が存在するとき、 $d$ は $a,b$ をともに割り切るので、 $c=ax+by$ を割り切る。逆に $d$ が $c$ を割り切るとき、補題 1.1により $ar+bs=d$ を満たす整数 $r,s$ を取ると、 $(x_0,y_0)=((c/d)r,(c/d)s)$ は整数解である。

任意の特殊解 $(x_0,y_0)$ を固定する。任意の整数 $t$ から定理の表示式で定めた $(x,y)$ は整数の組であり、

ax+by=ax_0+by_0+\frac{ab}{d}t-\frac{ab}{d}t=c

を満たす。任意の整数解 $(x,y)$ について、 $u=x-x_0$ , $v=y-y_0$ , $A=a/d$ , $B=b/d$ とおく。 $Au+Bv=0$ であり、上で取った整数 $r,s$ は $Ar+Bs=1$ を満たす。したがって

u=(Ar+Bs)u=B(su-rv),\qquad v=(Ar+Bs)v=-A(su-rv)

となる。整数 $t=su-rv$ を取ると、 $(x,y)$ は定理の表示式で表される。同じ解を与える二つの整数 $t,t'$ に対して $B(t-t')=A(t-t')=0$ となる。 $A,B$ の少なくとも一方は $0$ でないので、 $t=t'$ である。▨

注意 2.2. 一般解の表示で $t$ を $-t$ に置き換えても、 $t$ がすべての整数を動くことは変わらない。したがって、 $x=x_0-(b/d)t$ , $y=y_0+(a/d)t$ も同じ解の全体を表す。

注意 2.3. $a=b=0$ の場合、方程式は $0=c$ となる。 $c=0$ ならすべての整数の組が解であり、 $c\ne0$ なら解はない。

3 互除法からの計算

例 3.1. $1071x+1029y=21$ を解く。互除法により

$1071=1\times1029+42$
$1029=24\times42+21$
$42=2\times21+0$

であり、 $\gcd(1071,1029)=21$ である。余りの式を逆にたどると

21=1029-24\times42 =1029-24(1071-1029) =-24\times1071+25\times1029

となるので、 $(-24,25)$ は特殊解である。定理 2.1より、一般解は

x=-24+49t,\qquad y=25-51t\qquad(t\in\Z)

である。右辺が $63=3\times21$ の場合には、特殊解を $3$ 倍して $(-72,75)$ を得る。この場合の一般解は $x=-72+49t$ , $y=75-51t$ （ $t\in\Z$ ）である。

4 非負整数解

問題 4.1. 方程式 $7x+11y=100$ の非負整数解をすべて求めよ。また、 $7x+11y=10$ は整数解をもつが、非負整数解をもたないことを示せ。

解答.

$7\times(-3)+11\times11=100$ なので、定理 2.1より、第一の方程式の一般解は $x=-3+11t$ , $y=11-7t$ （ $t\in\Z$ ）である。整数 $t$ に対して、 $x\ge0$ は $t\ge1$ と同値であり、 $y\ge0$ は $t\le1$ と同値である。したがって $t=1$ に限られ、非負整数解は $(8,4)$ だけである。

第二の方程式では $7\times3+11\times(-1)=10$ なので整数解が存在し、定理 2.1より、一般解は $x=3+11t$ , $y=-1-7t$ （ $t\in\Z$ ）である。整数 $t$ に対して、 $x\ge0$ は $t\ge0$ と同値であり、 $y\ge0$ は $t\le-1$ と同値である。両方を満たす整数 $t$ は存在しないので、非負整数解はない。▨

閑話休題：ダイ・ハード3の水差しパズル 映画『ダイ・ハード3』には、爆弾を止めるために、3ガロンと5ガロンの容器だけを使って正確に4ガロンの水を作る場面がある。同じ容量の関係をもつ3リットルと5リットルの容器で、4リットルを量る操作を考える。

許された操作は、容器を満たすこと、空にすること、他方が満杯になるか注ぐ側が空になるまで水を移すこととする。 3Lと5Lの容器に入っている水量を、この順に組で表す。空の状態から

(0,0)\to(3,0)\to(0,3)\to(3,3)\to(1,5) \to(1,0)\to(0,1)\to(3,1)\to(0,4)

と操作すると、5Lの容器に4Lが残る。外から加えた水は3Lを3回、捨てた水は5Lを1回なので、残った水量は $3\times3-5=4$ である。この操作により、 $3x+5y=4$ の整数解 $(3,-1)$ に対応する水量が実現する。

6Lと9Lの容器では、空の状態から同じ種類の操作を何回行っても、それぞれの容器の水量は3の倍数である。満たす操作と空にする操作はこの性質を保つ。移す操作では、注ぐ側の水量と受ける側の空き容量はいずれも3の倍数であり、二つの量の小さい方だけ水を移すので、操作後の水量も3の倍数である。したがって4Lを量ることはできない。また、 $\gcd(6,9)=3$ は $4$ を割り切らないので、定理 2.1により $6x+9y=4$ に整数解はない。

§A4.3一次不定方程式 ax + by = c

1 一次不定方程式とベズーの等式

2 整数解の存在と一般解

3 互除法からの計算

4 非負整数解

例題

演習

前提記事