未知数が2つなのに方程式が1つしかないとき、解は無限にあるはずです。
しかし「整数解」に限ると、解が存在するための条件があり、すべての解を1つのパラメータで表せます。
整数 $a, b, c$ に対して、$ax + by = c$ を満たす整数 $x, y$ の組を求める問題を 2元1次不定方程式（以下、1次不定方程式）を解くといいます。
まず確認すべきは、整数解が存在するかどうかです。 たとえば $6x + 4y = 3$ を考えてみましょう。 左辺 $6x + 4y = 2(3x + 2y)$ は必ず偶数です。しかし右辺の $3$ は奇数。 偶数が奇数に等しくなることはありえないので、この方程式には整数解が存在しません。
$\gcd(a, b) = g$ とすると、$a = ga'$, $b = gb'$ と書けます。 このとき $ax + by = g(a'x + b'y)$ なので、左辺は必ず $g$ の倍数です。
したがって、$c$ が $g$ の倍数でなければ、等式は成り立ちません。 逆に $c$ が $g$ の倍数なら、解が存在することが証明できます。
存在条件：$ax + by = c$ が整数解をもつ $\Leftrightarrow$ $\gcd(a, b) \mid c$
$a, b$ を $0$ でない整数、$c$ を整数とする。$\gcd(a, b) = g$ とおくとき、
$$ax + by = c \text{ が整数解をもつ} \iff g \mid c$$
特に、$a$ と $b$ が互いに素（$g = 1$）なら、任意の整数 $c$ に対して整数解が存在する。
$a$ と $b$ が互いに素のとき、$ax + by = 1$ が整数解をもつことを示します。
[$\Leftarrow$] $b$ 個の整数 $a \cdot 1, a \cdot 2, a \cdot 3, \ldots, a \cdot (b-1)$ を $b$ で割った余りを考えます。
$a$ と $b$ は互いに素なので、これらの余りはすべて異なります（背理法で証明可能）。 余りは $0, 1, 2, \ldots, b-1$ の $b$ 通りしかないので、余りが $1$ となる $k$（$1 \leq k \leq b-1$）が存在します。
$a \cdot k = b \cdot q + 1$ とすると $a \cdot k + b \cdot (-q) = 1$。 よって $(x, y) = (k, -q)$ が $ax + by = 1$ の整数解です。
両辺に $c$ を掛ければ $a(ck) + b(-cq) = c$ となり、任意の $c$ について解が存在します。
[$\Rightarrow$] $ax + by = 1$ が整数解 $(x_0, y_0)$ をもつとします。 $\gcd(a, b) = g$ とすると $a = ga'$, $b = gb'$ で、$g(a'x_0 + b'y_0) = 1$。 $g$ は正の整数なので $g = 1$。すなわち $a, b$ は互いに素です。 $\square$
✕ 誤：$6x + 4y = 10$ は $\gcd(6, 4) = 2 \neq 1$ だから解なし。
○ 正：$\gcd(6, 4) = 2$ であり、$2 \mid 10$ なので解は存在します。 両辺を $2$ で割って $3x + 2y = 5$ とすれば、$\gcd(3, 2) = 1$ の不定方程式に帰着できます。
判定手順：$g = \gcd(a, b)$ を求める → $g \mid c$ を確認 → $g \mid c$ なら両辺を $g$ で割る → $a', b'$ が互いに素な方程式を解く
✕ 誤：$3x + 5y = 1$ の解は $(x, y) = (2, -1)$ の1組だけ。
○ 正：$(2, -1)$ は解の1つ（特殊解）に過ぎません。 整数解は無限に存在し、$(7, -4)$, $(-3, 2)$ なども解です。 すべての解を求めるには、Section 3 で学ぶ一般解の公式が必要です。
「不定方程式」は英語で Diophantine equation と呼ばれます。 これは古代ギリシアの数学者ディオファントス（3世紀頃）に由来する名前です。
ディオファントスは著書「算術」で整数解や有理数解を求める問題を多数扱いました。 17世紀にフェルマーがこの「算術」の余白に書き込んだメモが、 有名な「フェルマーの最終定理」（$x^n + y^n = z^n$ は $n \geq 3$ で正の整数解をもたない）の始まりです。
1次不定方程式を解く最初の関門は、1組の整数解（特殊解）を見つけることです。 特殊解さえ見つかれば、そこからすべての整数解を導けます。
$ax + by = c$ を解く手順は明確に2段階に分かれます。
Stage 1：方程式を満たす整数の組 $(x_0, y_0)$ を何でもいいから1組見つける（特殊解）。
Stage 2：特殊解と任意の解の差を取ることで、すべての解（一般解）を表す公式を導く。
Stage 1 のやり方はいくつかあります。直感で見つける、代入して探す、互除法の逆算を使う ── 方法は問いません。
係数が小さいときは、$x$ に小さな整数を代入して $y$ が整数になるか試すのが最速です。
例：$9x + 5y = 1$ の特殊解を求める。
$x = -1$ を代入：$9 \times (-1) + 5y = 1$ より $5y = 10$、$y = 2$。 よって $(x, y) = (-1, 2)$ が特殊解。
係数が大きいときは、9-5で学んだ互除法の逆算が威力を発揮します。 $67x + 107y = 3$ のように、直接代入では見つかりにくい場合に使います。
Step 1：$67$ と $107$ に互除法を適用。
$107 = 67 \times 1 + 40 \quad \cdots$ (i)
$67 = 40 \times 1 + 27 \quad \cdots$ (ii)
$40 = 27 \times 1 + 13 \quad \cdots$ (iii)
$27 = 13 \times 2 + 1 \quad \cdots$ (iv)
$\gcd(67, 107) = 1$。$1 \mid 3$ なので解は存在。
Step 2：逆算で $1 = 67 \cdot (\quad) + 107 \cdot (\quad)$ を導く。
(iv)' $\quad 1 = 27 - 13 \times 2$
(iii) を代入：$1 = 27 - (40 - 27) \times 2 = 27 \times 3 - 40 \times 2$
(ii) を代入：$1 = (67 - 40) \times 3 - 40 \times 2 = 67 \times 3 - 40 \times 5$
(i) を代入：$1 = 67 \times 3 - (107 - 67) \times 5 = 67 \times 8 + 107 \times (-5)$
Step 3：両辺に $3$ を掛ける。
$3 = 67 \times 24 + 107 \times (-15)$
よって $(x, y) = (24, -15)$ が $67x + 107y = 3$ の特殊解。
検算：$67 \times 24 + 107 \times (-15) = 1608 - 1605 = 3$ ✓
特殊解の取り方は一通りではありません。たとえば $3x + 5y = 43$ の特殊解として：
$(x, y) = (1, 8)$ でも $(6, 5)$ でも $(11, 2)$ でも正しいです。
どの特殊解を選んでも、一般解の表す整数解の集合は同じです。 見かけ上の式は異なりますが、パラメータ $t$ の置き換えで一致します。
$37x - 90y = 4$ のように一方の係数が大きいとき、互除法を完全に実行しなくても、 大きい係数を小さい方で割って係数を下げる方法があります。
$90 = 37 \times 2 + 16$ より $90y = 37 \times 2y + 16y$。 元の式に代入して $37(x - 2y) - 16y = 4$。$X = x - 2y$ とおくと $37X - 16y = 4$。 係数が $37, 16$ に減りました。これを繰り返せば特殊解が見つけやすくなります。
特殊解 $(x_0, y_0)$ が見つかったら、次はそこから一般解（すべての整数解）を導きます。 ここがこの記事の核心です。
$ax + by = c$ の特殊解を $(x_0, y_0)$ とします。つまり $ax_0 + by_0 = c$ です。 任意の整数解 $(x, y)$ との差を取ると：
$$a(x - x_0) + b(y - y_0) = 0$$$X = x - x_0$、$Y = y - y_0$ とおくと $aX + bY = 0$、すなわち $aX = -bY$ です。
$a$ と $b$ が互いに素のとき、$aX = -bY$ から $X$ は $b$ の倍数でなければなりません （$a$ と $b$ は互いに素で、$a$ が $bY$ を割り切るので、$a$ は $Y$ を割り切る ── ではなく、 $b$ が $aX$ を割り切り、$b$ と $a$ が互いに素なので $b$ が $X$ を割り切ります）。
したがって $X = bt$（$t$ は整数）とおけます。$aX = -bY$ に代入すると $abt = -bY$、$Y = -at$。
$a$ と $b$ が互いに素で、$ax_0 + by_0 = c$ を満たす整数 $(x_0, y_0)$ が存在するとき、
$$ax + by = c \text{ の整数解は } \begin{cases} x = x_0 + bt \\ y = y_0 - at \end{cases} \quad (t \text{ は任意の整数})$$
一般解の公式 $x = x_0 + bt$, $y = y_0 - at$ の構造を分解すると：
$(x_0, y_0)$ ＝ $ax + by = c$ の特殊解（1組の具体的な解）
$(bt, -at)$ ＝ $ax + by = 0$ の一般解（同次方程式の解）
つまり、一般解 ＝ 特殊解 ＋ 同次方程式の解です。 この構造は、微分方程式の一般解（特殊解＋斉次解）や、 連立方程式の解の構造（特殊解＋核空間）と本質的に同じです。
Step 1：特殊解を見つける。
$x = 1$ を代入：$3 + 5y = 43$、$5y = 40$、$y = 8$。特殊解 $(x_0, y_0) = (1, 8)$。
Step 2：差を取る。
$3 \cdot 1 + 5 \cdot 8 = 43 \quad \cdots$ (特殊解)
$3x + 5y = 43 \quad \cdots$ (一般の解)
辺々引いて $3(x - 1) + 5(y - 8) = 0$
$3(x - 1) = -5(y - 8)$
$3$ と $5$ は互いに素だから $x - 1$ は $5$ の倍数。$x - 1 = 5t$ とおくと $y - 8 = -3t$。
一般解：
$$\begin{cases} x = 5t + 1 \\ y = -3t + 8 \end{cases} \quad (t \text{ は整数})$$
検算：$3(5t+1) + 5(-3t+8) = 15t + 3 - 15t + 40 = 43$ ✓
一般解 $x = x_0 + bt$, $y = y_0 - at$ で最も多いミスは符号です。
✕ 誤：$3x + 5y = 43$ の一般解を $x = 5t + 1$, $y = 3t + 8$ としてしまう（$y$ の $t$ の符号が正）。
○ 正：$x = 5t + 1$, $y = -3t + 8$（$y$ の $t$ の係数は $-a = -3$）。
覚え方：$x$ が $+b$ ずつ増えるとき、$y$ は $-a$ ずつ変わる。 $ax + by = c$ を満たし続けるには、$a$ の増分を $b$ の減分で相殺する必要があるからです。
検算法：一般解を元の方程式に代入して、$t$ が消えて $c$ だけが残ることを確認しましょう。 $t$ が残ったら、どこかで符号を間違えています。
$\gcd(a, b) = g > 1$ のとき、$g \mid c$ なら両辺を $g$ で割ります。
例：$6x + 10y = 14$ → $\gcd(6, 10) = 2$、$2 \mid 14$ なので $3x + 5y = 7$ に帰着。 特殊解 $(x_0, y_0) = (4, -1)$（$3 \times 4 + 5 \times (-1) = 7$）。 一般解：$x = 5t + 4$, $y = -3t - 1$。
$3x + 5y = 43$ の整数解は、直線 $y = -\frac{3}{5}x + \frac{43}{5}$ 上の格子点 （$x, y$ がともに整数の点）に対応します。
直線の傾きが $-\frac{3}{5}$（既約分数）なので、$x$ が $5$ 増えるごとに $y$ が $3$ 減ります。 つまり格子点は等間隔に並んでおり、1つ見つければ $+5, -3$ のステップで次々に見つかります。 これがまさに一般解の $(bt, -at)$ の幾何学的な意味です。
入試では「整数解を求めよ」だけでなく、 「自然数の解を求めよ」「正の整数解の個数を求めよ」と聞かれることがよくあります。
自然数解を求めるには、一般解に $x > 0$ かつ $y > 0$（または $x \geq 1$ かつ $y \geq 1$）の条件を課し、 パラメータ $t$ の範囲を求めます。
一般解は $t$ を使ってすべての整数解を表しています。 自然数の制約を課すことは、$t$ に対する連立不等式を解くことに帰着します。
$x = x_0 + bt > 0$ かつ $y = y_0 - at > 0$ を同時に満たす整数 $t$ の範囲を求め、 その中の整数の個数を数えればよいのです。
一般解：$x = 5t + 1$, $y = -3t + 8$（$t$ は整数）
$x > 0$ より $5t + 1 > 0$、$t > -\dfrac{1}{5}$
$y > 0$ より $-3t + 8 > 0$、$t < \dfrac{8}{3}$
$-\dfrac{1}{5} < t < \dfrac{8}{3}$ を満たす整数は $t = 0, 1, 2$。
$t = 0$：$(x, y) = (1, 8)$
$t = 1$：$(x, y) = (6, 5)$
$t = 2$：$(x, y) = (11, 2)$
よって自然数解は $3$ 組。
一般解が $x = -5t + 24$ のように $t$ の係数が負のとき、$x > 0$ は
✕ 誤：$-5t + 24 > 0$ → $t > \dfrac{24}{5}$（不等号の向きを変えず割った）
○ 正：$-5t + 24 > 0$ → $-5t > -24$ → $t < \dfrac{24}{5}$（負の数で割ると不等号が逆転）
鉄則：負の数で割るときは不等号の向きを逆にする。 この基本ルールを忘れると、$t$ の範囲が完全に逆になります。
問題によっては $x \geq 0$, $y \geq 0$ を求めることもあります。 このときは不等号を $\geq$ にして同様に $t$ の範囲を求めます。 等号が成り立つ場合（$x = 0$ や $y = 0$）も解に含まれるかどうか、問題文をよく確認しましょう。
「$ax + by = c$ の自然数解」は、実社会では整数計画問題と呼ばれる分野の一部です。 たとえば「80円切手と120円切手を合わせて1000円ちょうどで買う方法」は $80x + 120y = 1000$ の非負整数解を求める問題です。
大学の最適化理論や経済学では、こうした整数条件つきの最適化問題を体系的に扱います。 高校で学ぶ不定方程式は、その最も基本的な形です。
1次不定方程式の解法を俯瞰し、さまざまな不定方程式のパターンを整理しましょう。
| パターン | 方程式の形 | 解法のポイント |
|---|---|---|
| A：2元1次（基本） | $ax + by = c$ | 特殊解を見つけ、一般解の公式を適用 |
| B：2元1次（互除法） | $ax + by = c$（係数大） | 互除法の逆算で特殊解を求める |
| C：積の形 | $xy + ax + by = c$ | $(\quad)(\quad) = \text{(整数)}$ に変形して約数で絞り込む |
| D：3元以上 | $ax + by + cz = d$ | 値の範囲で候補を絞り、2元に帰着 |
| E：自然数解 | $ax + by = c$（$x, y > 0$） | 一般解に不等式制約を課し $t$ の範囲を求める |
| F：応用（余り条件） | 割り算の条件から立式 | 余り条件を不定方程式に翻訳してから解く |
Q1. $6x + 4y = 3$ に整数解が存在しない理由を述べてください。
Q2. $9x + 5y = 1$ の整数解をすべて求めてください。
Q3. 一般解の公式で、$x$ の変化量が $+b$ で $y$ の変化量が $-a$ になるのはなぜですか？
Q4. $3x + 5y = 43$ の自然数解（$x > 0, y > 0$）は何組ありますか？
Q5. $12x + 8y = 20$ の整数解をすべて求めてください。
この記事で学んだ内容を、入試形式の問題で確認しましょう。
次の方程式の整数解をすべて求めよ。
(1) $7x + 6y = 40$
(2) $4x - 5y = 1$
(1) $x = 6t + 4$, $y = -7t + 2$（$t$ は整数）
(2) $x = -5t + 4$, $y = -4t + 3$（$t$ は整数）
(1) $7 \times 4 + 6 \times 2 = 28 + 12 = 40$ より $(x_0, y_0) = (4, 2)$。
$7(x - 4) + 6(y - 2) = 0$ すなわち $7(x - 4) = -6(y - 2)$。
$7$ と $6$ は互いに素だから $x - 4 = 6t$。$y - 2 = -7t$。
$x = 6t + 4$, $y = -7t + 2$。検算：$7(6t+4)+6(-7t+2) = 42t+28-42t+12 = 40$ ✓
(2) $4 \times 4 - 5 \times 3 = 16 - 15 = 1$ より $(x_0, y_0) = (4, 3)$。
$4(x - 4) - 5(y - 3) = 0$ すなわち $4(x - 4) = 5(y - 3)$。
$4$ と $5$ は互いに素だから $x - 4 = 5s$。ここで $4 \cdot 5s = 5(y-3)$ より $y - 3 = 4s$。
ただし $4x - 5y = 1$ なので一般解の公式に注意。$b = -5$ なので $x = x_0 + (-5)t$? いいえ、ここでは $4x + (-5)y = 1$ と見て、$a = 4, b = -5$。
正しくは：$4(x-4) = 5(y-3)$。$x - 4 = 5t$, $y - 3 = 4t$。
$x = 5t + 4$, $y = 4t + 3$。検算：$4(5t+4) - 5(4t+3) = 20t+16-20t-15 = 1$ ✓
$x = 5t + 4$, $y = 4t + 3$（$t$ は整数）。
方程式 $5x + 7y = 2012$ を満たす自然数の組 $(x, y)$ はいくつあるか。
$57$ 組
方針：特殊解を求めて一般解を書き、$x > 0$, $y > 0$ で $t$ の範囲を絞る。
$\gcd(5, 7) = 1$ なので解は存在する。
特殊解：$5 \times 3 + 7 \times (-1) = 15 - 7 = 8 \neq 2012$。
$5 \times 1 + 7 \times 1 = 12$。$2012 = 12 \times ?$ ではないので直接的に倍数にはならない。
$x = 2$ のとき $10 + 7y = 2012$、$7y = 2002$、$y = 286$。特殊解 $(2, 286)$。
一般解：$x = 7t + 2$, $y = -5t + 286$。
$x > 0$ より $7t + 2 > 0$、$t > -\dfrac{2}{7}$、$t \geq 0$。
$y > 0$ より $-5t + 286 > 0$、$t < \dfrac{286}{5} = 57.2$、$t \leq 57$。
$t = 0, 1, 2, \ldots, 57$ の $58$ 個... ではなく、$t \geq 0$ かつ $t \leq 57$ なので $t = 0, 1, \ldots, 57$ の $58$ 個。
ただし $t = 0$：$(2, 286)$。$t = 57$：$(7 \times 57 + 2, -5 \times 57 + 286) = (401, 1)$。$x > 0, y > 0$ ✓。
検算：$5 \times 401 + 7 \times 1 = 2005 + 7 = 2012$ ✓。
$t = 0$ から $t = 57$ まで $58$ 個。
答え：$58$ 組。
$11$ で割ると $2$ 余り、$7$ で割ると $6$ 余るような3桁の自然数 $N$ の最大値と最小値を求めよ。
最小値 $167$、最大値 $937$
方針：余り条件を方程式に翻訳し、不定方程式として解く。
$N = 11a + 2$（$a$ は非負整数）、$N = 7b + 6$（$b$ は非負整数）。
$11a + 2 = 7b + 6$ より $11a - 7b = 4 \quad \cdots$ (*)
$a = 1, b = 1$ のとき $11 - 7 = 4$ ✓。特殊解 $(a, b) = (1, 1)$。
一般解：$a = 7t + 1$, $b = 11t + 1$（$t$ は整数）。
$N = 11(7t + 1) + 2 = 77t + 13$。
3桁の自然数：$100 \leq 77t + 13 \leq 999$。
$87 \leq 77t \leq 986$、$\dfrac{87}{77} \leq t \leq \dfrac{986}{77}$、$1.13 \leq t \leq 12.8$。
$t = 2, 3, \ldots, 12$。
最小値：$t = 2$ のとき $N = 77 \times 2 + 13 = 167$。
最大値：$t = 12$ のとき $N = 77 \times 12 + 13 = 937$。
方程式 $17x - 36y = 1$ の整数解をすべて求めよ。
$x = 36t + 17$, $y = 17t + 8$（$t$ は整数）
方針：係数が大きいので互除法の逆算で特殊解を求める。
Step 1：$36$ と $17$ に互除法を適用。
$36 = 17 \times 2 + 2 \quad \cdots$ (i)
$17 = 2 \times 8 + 1 \quad \cdots$ (ii)
$\gcd(36, 17) = 1$ ✓
Step 2：逆算。
(ii)' $\quad 1 = 17 - 2 \times 8$
(i) より $2 = 36 - 17 \times 2$ を代入：
$1 = 17 - (36 - 17 \times 2) \times 8 = 17 \times 17 - 36 \times 8$
すなわち $17 \times 17 - 36 \times 8 = 1$。
$(x_0, y_0) = (17, 8)$ が特殊解。検算：$17 \times 17 - 36 \times 8 = 289 - 288 = 1$ ✓
Step 3：一般解の導出。
$17(x - 17) - 36(y - 8) = 0$ すなわち $17(x - 17) = 36(y - 8)$。
$17$ と $36$ は互いに素だから $x - 17 = 36t$、$y - 8 = 17t$。
$x = 36t + 17$, $y = 17t + 8$（$t$ は整数）。
検算：$17(36t+17) - 36(17t+8) = 612t + 289 - 612t - 288 = 1$ ✓