1 次不定方程式の整数解

互除法などで特殊解を 1 つ見つけ、 $a x + b y = c$ の整数解をすべて $x = x_{0} + bk, y = y_{0} - ak$ （ $a, b$ は互いに素, $k$ は整数）の形で表せる

前提

ユークリッドの互除法（数学A 整数の性質）

この技能までの道筋（5 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
ユークリッドの互除法（数学A 整数の性質）

説明

$a x + b y = c$ （ $a, b, c$ は整数）のように、解が無数にある 1 次方程式について、整数の解 $(x, y)$ をすべて求められるようになります。まず互除法を使って解を 1 組（特殊解）見つけます。次に、その解からほかの解がどれだけずれているかを調べ、すべての解を整数 $k$ を使って表します。「何個かずつ買って合計金額をちょうどにする」「ある数で割った余りの条件を満たす数を探す」といった問題で使います。

なぜそうしてよいのか

解を 1 組見つけられる理由　互除法では、割り算 $a = b q + r$ を続けて余りを小さくしていきます。どの段階の余りも「 $a$ の整数倍 $+$ $b$ の整数倍」の形で書けます（ $r = a - b q$ で、次の余りも前の 2 つの余りから同じように作られるからです）。 $a, b$ が互いに素なら、最後に余り $1$ が現れるので、 $a x^{'} + b y^{'} = 1$ となる整数 $x^{'}, y^{'}$ が見つかります。両辺を $c$ 倍すれば $a (c x^{'}) + b (c y^{'}) = c$ となり、 $x_{0} = c x^{'}, y_{0} = c y^{'}$ が $a x + b y = c$ の解の 1 つ（特殊解）になります。

すべての解が $x = x_{0} + bk, y = y_{0} - ak$ になる理由　 $(x, y)$ を任意の整数解とします。 $a x + b y = c$ から $a x_{0} + b y_{0} = c$ を引くと $a (x - x_{0}) = b (y_{0} - y)$ です。右辺は $b$ の倍数なので、左辺 $a (x - x_{0})$ も $b$ の倍数です。ところが $a$ と $b$ は互いに素なので、 $b$ の素因数は $a$ に 1 つも含まれていません。したがって $b$ の素因数はすべて $x - x_{0}$ が受け持つことになり、 $x - x_{0}$ は $b$ の倍数です。これを $x - x_{0} = bk$ （ $k$ は整数）とおいて代入すると $abk = b (y_{0} - y)$ となり、 $b \neq = 0$ で割って $y_{0} - y = ak$ を得ます。逆に、どんな整数 $k$ でも $a (x_{0} + bk) + b (y_{0} - ak) = a x_{0} + b y_{0} = c$ が成り立つので、これらはすべて解です。

互いに素でないとき　 $g cd (a, b) = d > 1$ の場合、左辺 $a x + b y$ はいつも $d$ の倍数です。そのため $c$ が $d$ の倍数でなければ、整数解はありません。 $c$ が $d$ の倍数なら、両辺を $d$ で割って互いに素な係数の式に直してから考えます。

手順

係数の最大公約数 $d = g cd (a, b)$ を調べる。 $c$ が $d$ で割り切れなければ整数解はない。割り切れるなら両辺を $d$ で割り、 $a, b$ が互いに素な形にする
$a, b$ に互除法を行い、余りが $1$ になるまでの割り算の式を書き並べる
割り算の式を下から逆にたどって代入し、 $a x^{'} + b y^{'} = 1$ を満たす整数 $x^{'}, y^{'}$ を見つける
両辺を $c$ 倍して特殊解 $x_{0} = c x^{'}, y_{0} = c y^{'}$ を得る（ $a x_{0} + b y_{0} = c$ を代入して確かめる）
元の式から $a x_{0} + b y_{0} = c$ を引いて $a (x - x_{0}) = b (y_{0} - y)$ とし、 $a, b$ が互いに素であることから $x = x_{0} + bk, y = y_{0} - ak$ （ $k$ は整数）と表す
問題に条件（正の整数、最小など）があれば、それを満たすように $k$ の値を決める

例題

方程式 $17 x + 12 y = 3$ の整数解のうち、 $x$ が正で最小となるものを $(x, y)$ の組で求めよ。

例題の解答

【手順1】 $17 = 12 \cdot 1 + 5$ なので $g cd (17, 12) = g cd (12, 5) = 1$ 。 $17$ と $12$ は互いに素で、そのまま進める。
【手順2】互除法を行う。 $17 = 12 \cdot 1 + 5$ 、 $12 = 5 \cdot 2 + 2$ 、 $5 = 2 \cdot 2 + 1$ 。
【手順3】下から逆にたどる。 $1 = 5 - 2 \cdot 2$ に $2 = 12 - 5 \cdot 2$ を代入すると $1 = 5 - 2 (12 - 5 \cdot 2) = 5 \cdot 5 - 12 \cdot 2$ 。さらに $5 = 17 - 12$ を代入すると $1 = 5 (17 - 12) - 12 \cdot 2 = 17 \cdot 5 - 12 \cdot 7$ 。よって $17 \cdot 5 + 12 \cdot (- 7) = 1$ である。
【手順4】両辺を $3$ 倍して $17 \cdot 15 + 12 \cdot (- 21) = 3$ を得る。特殊解は $x_{0} = 15, y_{0} = - 21$ （確認： $255 - 252 = 3$ ）。
【手順5】 $17 x + 12 y = 3$ から $17 \cdot 15 + 12 \cdot (- 21) = 3$ を引くと $17 (x - 15) = 12 (- 21 - y)$ 。 $17$ と $12$ は互いに素なので $x - 15$ は $12$ の倍数であり、 $x - 15 = 12 k$ とおける。代入すると $17 \cdot 12 k = 12 (- 21 - y)$ となり、 $- 21 - y = 17 k$ を得る。よって一般解は $x = 15 + 12 k, y = - 21 - 17 k$ （ $k$ は整数）。
【手順6】 $x = 15 + 12 k > 0$ より $k > - \frac{15}{12}$ で、これを満たす最小の整数は $k = - 1$ 。このとき $x$ は最小になり、 $x = 15 - 12 = 3$ 、 $y = - 21 + 17 = - 4$ 。確認すると $17 \cdot 3 + 12 \cdot (- 4) = 51 - 48 = 3$ で、確かに解になっている。
答え： $(x, y) = (3, - 4)$

答え: $(3, - 4)$

よくある誤り

$x$ と $y$ に足す係数を取り違えて $x = x_{0} + ak, y = y_{0} - bk$ としてしまう誤り。正しくは $a (x - x_{0}) = b (y_{0} - y)$ から $x - x_{0}$ が $b$ の倍数になるので、 $x = x_{0} + bk, y = y_{0} - ak$ である。例えば $17 x + 12 y = 3$ では $x = 15 + 12 k, y = - 21 - 17 k$ となる。代入して $k$ が消えることを必ず確かめる。
$a x^{'} + b y^{'} = 1$ の解をそのまま $a x + b y = c$ の解としてしまう誤り。正しくは両辺を $c$ 倍し、 $x_{0} = c x^{'}, y_{0} = c y^{'}$ とする。例えば $17 \cdot 5 + 12 \cdot (- 7) = 1$ から $17 x + 12 y = 3$ の特殊解を求めると、 $(5, - 7)$ ではなく $(15, - 21)$ である。
係数が互いに素でないまま公式に当てはめてしまう誤り。例えば $6 x + 4 y = 2$ で $x = x_{0} + 4 k$ とすると、 $x$ を $4$ ずつしか動かさないので解の半分を取りこぼす。正しくは両辺を $g cd (6, 4) = 2$ で割って $3 x + 2 y = 1$ とし、 $x = 1 + 2 k, y = - 1 - 3 k$ （ $k$ は整数）とする。また $6 x + 4 y = 3$ のように $c$ が $g cd (a, b)$ で割り切れないときは、整数解は存在しない。
一般解を書くときに「 $k$ は整数」を書き落とす、または $k$ を $0$ 以上の整数だけに限ってしまう誤り。 $k$ は負の整数も含むすべての整数をとる。例題で $x$ が正で最小となる解は $k = - 1$ のときの $(3, - 4)$ であり、 $k = 0$ のときの $(15, - 21)$ ではない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

不定方程式の正の整数解の個数と選び出し（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）