1次不定方程式 | 高校数学まるごと解説

要点整理

前提知識として、すでに「ユークリッドの互除法」(2つの整数の最大公約数を、割り算のあまりを使って効率よく求める方法)を学習済みですね。ここでは、その考え方を利用して、$ax+by=c$ の形をした方程式の整数解をすべて求める方法を整理していきます。このような方程式を1次不定方程式といいます。

1次不定方程式とは

$a, b, c$ を整数の定数とするとき、

$ax+by=c$

を満たす整数の組 $(x, y)$ をすべて求める問題を考えます。文字が $x, y$ の2つあるのに、式は1本しかないので、ふつうは解が1組には定まりません。このため「不定」方程式と呼ばれています。

整数解をもつための条件

$a$ と $b$ の最大公約数を $d$ とします。最大公約数は $\gcd(a,b)$ という記号で表すこともあるので、$d=\gcd(a,b)$ とも書きます。このとき、次のことが成り立ちます。

$ax+by=c \text{ が整数解をもつ} \iff d \text{ は } c \text{ を割り切る}$

なぜこうなるのかを確認しておきましょう。$d$ は $a$ と $b$ の両方の約数なので、$x, y$ にどんな整数を入れても、$ax+by$ の値は必ず $d$ の倍数になります。したがって、$c$ が $d$ の倍数でなければ、$ax+by=c$ を満たす整数 $x, y$ は存在しません。

逆に $c$ が $d$ の倍数であれば、必ず整数解が存在します。これは、ユークリッドの互除法の計算を後ろから代入していくと、最大公約数 $d$ を $d=ap+bq$(ここで $p, q$ は整数)という形に必ず表せる、という事実を使うと示すことができます。

特殊解の見つけ方

実際に方程式を解くときは、まず1組だけ整数解を見つけます。これを特殊解といいます。特殊解は、

数が小さいときは、あてはめて探す
数が大きいときは、ユークリッドの互除法の計算を後ろから代入していく

という2通りの方法で見つけることができます。後者のやり方は、例題2で具体的に確認します。

一般解の求め方

特殊解が1組 $(x_0, y_0)$ 見つかったとします。つまり、

$ax_0+by_0=c$

が成り立っています。求めたいすべての解を $(x, y)$ とすると、

$ax+by=c$

も成り立っています。この2つの式の両辺どうしをそれぞれ引くと、

$a(x-x_0)+b(y-y_0)=0$

という式が得られます(右辺は $c-c=0$ になります)。この式を移項すると、

$a(x-x_0)=-b(y-y_0)$

となります。$d=\gcd(a,b)$ として $a=da'$、$b=db'$ とおくと($a'$、$b'$ はそれぞれ $\dfrac{a}{d}$、$\dfrac{b}{d}$ のことです)、$a'$ と $b'$ は互いに素(最大公約数が1)になります。両辺を $d$ で割ると、

$a'(x-x_0)=-b'(y-y_0)$

右辺は $b'$ の倍数なので、左辺の $a'(x-x_0)$ も $b'$ の倍数でなければなりません。$a'$ と $b'$ は互いに素なので、「$a'(x-x_0)$ が $b'$ の倍数である」ことと、「$x-x_0$ が $b'$ の倍数である」ことは同値です。そこで、整数 $t$ を使って、

$x-x_0=b't$

とおけます。これを $a'(x-x_0)=-b'(y-y_0)$ に代入すると、

$a'b't=-b'(y-y_0)$

両辺を $b'$ で割ると、

$a't=-(y-y_0)$

となるので、$y-y_0=-a't$ です。$a'=\dfrac{a}{d}$、$b'=\dfrac{b}{d}$ をもとに戻すと、次の一般解の公式が得られます。

$x = x_0 + \frac{b}{d}t, \qquad y = y_0 - \frac{a}{d}t \qquad (t \text{は整数})$

$t$ に $\ldots,-2,-1,0,1,2,\ldots$ を代入すると、方程式を満たすすべての整数解が得られます。

例題

例題1(基本)

問題

$3x+5y=1$ を満たす整数 $x, y$ の組をすべて求めなさい。

解答・解説を見る

まず特殊解を1組見つけます。$3$ と $5$ は小さい数なので、あてはめて探してみます。$x=2, y=-1$ のとき、

$3\times2+5\times(-1)=6-5=1$

となり成り立ちます。よって $(x_0, y_0)=(2,-1)$ は特殊解の1つです。

次に $3$ と $5$ の最大公約数を確認します。$3$ と $5$ に共通する約数は $1$ しかないので、最大公約数は $d=1$ です。

一般解の公式 $x=x_0+\dfrac{b}{d}t$、$y=y_0-\dfrac{a}{d}t$ に、$a=3$、$b=5$、$d=1$、$x_0=2$、$y_0=-1$ を代入すると、

$x=2+\frac{5}{1}t=2+5t$

$y=-1-\frac{3}{1}t=-1-3t$

よって、求める整数解は、

$(x,y)=(2+5t,\ -1-3t)\quad(t\ \text{は整数})$

です。

(検算: $t=1$ のとき $(x,y)=(7,-4)$ となり、$3\times7+5\times(-4)=21-20=1$ で確かに成り立っています。)

例題2(標準)

問題

$7x+4y=1$ を満たす整数 $x, y$ の組をすべて求めなさい。ただし、特殊解はユークリッドの互除法を利用して見つけなさい。

解答・解説を見る

ステップ1: ユークリッドの互除法で最大公約数を求める

$7$ と $4$ に、ユークリッドの互除法を使います。

$7=4\times1+3$

$4=3\times1+1$

$3=1\times3+0$

あまりが $0$ になったので、最後に割った数である $1$ が最大公約数です。$d=\gcd(7,4)=1$ で、$c=1$ もこの $1$ で割り切れるので、整数解が存在することが確認できます。

ステップ2: 互除法の式を後ろから代入して特殊解を作る

1つ目の式 $7=4\times1+3$ を、あまり $3$ について解くと、

$3=7-4\times1$

2つ目の式 $4=3\times1+1$ を、あまり $1$ について解くと、

$1=4-3\times1$

この式の $3$ に、上で求めた $3=7-4\times1$ を代入すると、

$1=4-(7-4\times1)\times1$

右辺のかっこを外すと、

$1=4-7+4$

$4$ の項をまとめると、

$1=4\times2-7\times1$

これは $7\times(-1)+4\times2=1$ と書き直せます。つまり $x_0=-1$、$y_0=2$ は特殊解です。

(検算: $7\times(-1)+4\times2=-7+8=1$ で確かに成り立っています。)

ステップ3: 一般解を作る

$a=7$、$b=4$、$d=1$ なので、一般解の公式に代入すると、

$x=x_0+\frac{b}{d}t=-1+4t$

$y=y_0-\frac{a}{d}t=2-7t$

よって、求める整数解は、

$(x,y)=(-1+4t,\ 2-7t)\quad(t\ \text{は整数})$

です。

例題3(応用)

問題

$3x+5y=31$ を満たす $0$ 以上の整数の組 $(x, y)$ をすべて求めなさい。

解答・解説を見る

ステップ1: 特殊解を見つける

まず、$0$ 以上という条件をいったん外して、整数解全体を求めます。あてはめて探すと、$x=2, y=5$ のとき、

$3\times2+5\times5=6+25=31$

となり成り立つので、$(x_0,y_0)=(2,5)$ は特殊解の1つです。

ステップ2: 一般解を作る

$3$ と $5$ の最大公約数は $d=1$ です。一般解の公式に $a=3$、$b=5$、$d=1$ を代入すると、

$x=2+\frac{5}{1}t=2+5t$

$y=5-\frac{3}{1}t=5-3t$

よって、整数解全体は $(x,y)=(2+5t,\ 5-3t)$($t$ は整数)です。

ステップ3: $x\geq0$ かつ $y\geq0$ となる $t$ の範囲を絞り込む

問題の条件は「$0$ 以上の整数」なので、$x\geq0$ と $y\geq0$ を同時に満たす $t$ を探します。

$x\geq0$ より、

$2+5t\geq0$

両辺から $2$ を引くと、

$5t\geq-2$

両辺を $5$ で割ると、

$t\geq-\frac{2}{5}$

$t$ は整数なので、これを満たす最小の整数は $t=0$ です。つまり $t\geq0$ です。

$y\geq0$ より、

$5-3t\geq0$

両辺から $5$ を引くと、

$-3t\geq-5$

両辺を $-3$ で割ります。負の数で割るので、不等号の向きが逆になることに注意すると、

$t\leq\frac{5}{3}$

$\dfrac{5}{3}=1.66\ldots$ なので、$t$ は整数であることから $t\leq1$ です。

ステップ4: 範囲に入る $t$ をすべて調べる

$t\geq0$ と $t\leq1$ を合わせると、$t=0$ または $t=1$ です。

$t=0$ のとき: $x=2+5\times0=2$、$y=5-3\times0=5$ より $(x,y)=(2,5)$
$t=1$ のとき: $x=2+5\times1=7$、$y=5-3\times1=2$ より $(x,y)=(7,2)$

(検算: $(7,2)$ について $3\times7+5\times2=21+10=31$ で確かに成り立っています。)

よって、求める組は、

$(x,y)=(2,5),\ (7,2)$

の2組です。

練習問題

問題

$8x+5y=1$ を満たす整数 $x, y$ の一般解を求めなさい。ただし、特殊解はユークリッドの互除法を利用して見つけなさい。

答え

$(x,y)=(2+5t,\ -3-8t)$($t$ は整数)。

(ユークリッドの互除法より $\gcd(8,5)=1$ で、互除法の式を後ろから代入すると特殊解の1つとして $x_0=2$、$y_0=-3$ が得られます。$8\times2+5\times(-3)=16-15=1$ で確かに成り立っています。)