一次不定方程式とn進法【ディオファントス方程式・基数変換】

整数の性質の応用として、一次不定方程式（整数解をもつ1次方程式）とn進法（数の表し方の変換）は、入試でも頻出のテーマです。ユークリッドの互除法との連携も含めて、段階的に理解しましょう。

---

1. 一次不定方程式とは

1.1. 定義

整数係数の方程式 $ax + by = c$（$a$、$b$、$c$ は整数、$a \neq 0$、$b \neq 0$）の整数解（$x$、$y$ がともに整数になる解）を求める問題を一次不定方程式（ディオファントス方程式）といいます。

「不定」とは解が1つに決まらない（無数に存在しうる）という意味です。

1.2. 解の存在条件

$$ax + by = c \text{ が整数解をもつ} \Leftrightarrow \gcd(a, b) \mid c$$

つまり、$c$ が $\gcd(a, b)$ の倍数であることが必要十分条件です。

---

2. 一次不定方程式の解法

2.1. ステップ1：特殊解を1つ見つける

まず $ax + by = c$ を満たす1組の整数解（特殊解）$(x_0, y_0)$ を見つけます。

特殊解の見つけ方：

• 試行錯誤（係数が小さい場合）
• ユークリッドの互除法の逆手順（一般的な方法）

2.2. ステップ2：一般解を書く

$(x_0, y_0)$ が特殊解のとき、一般解は次の形になります：

$$x = x_0 + \frac{b}{\gcd(a,b)} t, \quad y = y_0 - \frac{a}{\gcd(a,b)} t \quad (t \in \mathbb{Z})$$

特に $\gcd(a, b) = 1$ のとき：

$$x = x_0 + bt, \quad y = y_0 - at \quad (t \in \mathbb{Z})$$

2.3. 例題1：基本的な一次不定方程式

問題： $3x + 5y = 1$ の整数解をすべて求めよ。

解答：

特殊解を見つける： $x = 2$、$y = -1$ のとき、$3(2) + 5(-1) = 6 - 5 = 1$ ✓

特殊解：$(x_0, y_0) = (2, -1)$

一般解： $\gcd(3, 5) = 1$ なので：

$$x = 2 + 5t, \quad y = -1 - 3t \quad (t \in \mathbb{Z})$$

---

3. ユークリッドの互除法を使った特殊解の求め方

3.1. 互除法の逆手順

$\gcd(a, b)$ をユークリッドの互除法で求める際の計算を逆にたどることで、$ax + by = \gcd(a,b)$ の特殊解を得られます。

3.2. 例題2：互除法を使う一次不定方程式

問題： $17x + 5y = 1$ の整数解を求めよ。

解答：

ユークリッドの互除法：

$$17 = 3 \times 5 + 2$$ $$5 = 2 \times 2 + 1$$ $$2 = 2 \times 1 + 0$$

$\gcd(17, 5) = 1$ を確認。逆手順で1を表す：

$$1 = 5 - 2 \times 2$$ $$= 5 - 2 \times (17 - 3 \times 5)$$ $$= 5 - 2 \times 17 + 6 \times 5$$ $$= 7 \times 5 - 2 \times 17$$ $$= 17 \times (-2) + 5 \times 7$$

特殊解：$(x_0, y_0) = (-2, 7)$

一般解：

$$x = -2 + 5t, \quad y = 7 - 17t \quad (t \in \mathbb{Z})$$

3.3. 例題3：条件付きの一次不定方程式

問題： $3x + 7y = 11$ の正の整数解を求めよ。

解答：

まず特殊解を1つ求める。$x = 6$、$y = -1$ のとき $3(6) + 7(-1) = 18 - 7 = 11$ ✓

一般解：

$$x = 6 + 7t, \quad y = -1 - 3t \quad (t \in \mathbb{Z})$$

$x > 0$、$y > 0$ の条件：

$$x = 6 + 7t > 0 \Rightarrow t > -\frac{6}{7} \Rightarrow t \geq 0$$ $$y = -1 - 3t > 0 \Rightarrow -3t > 1 \Rightarrow t < -\frac{1}{3} \Rightarrow t \leq -1$$

両方を同時に満たす $t$ の値は存在しない。

$\therefore$ 正の整数解は存在しない。

---

4. n進法

4.1. n進法とは

私たちが普段使う数は10進法（0〜9の10種類の数字を使い、10になると繰り上がる）です。

n進法は、$n$ 種類の数字（$0$ から $n-1$）を使い、$n$ になると繰り上がる記数法です。

4.2. n進法の位の値

$n$ 進法での数 $\overline{a_k a_{k-1} \cdots a_1 a_0}_{(n)}$ の10進法での値は：

$$a_k \times n^k + a_{k-1} \times n^{k-1} + \cdots + a_1 \times n^1 + a_0 \times n^0$$

---

5. 基数変換

5.1. n進法 → 10進法

各桁の数字に $n$ の冪乗を掛けて足す。

5.2. 例題4：2進法を10進法に変換

問題： $1101_{(2)}$ を10進法で表せ。

解答：

$$1101_{(2)} = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$$ $$= 8 + 4 + 0 + 1 = 13$$

5.3. 10進法 → n進法

n で繰り返し割り算して余りを並べる（最後の商から逆順に）。

5.4. 例題5：10進法を2進法に変換

問題： 13 を2進法で表せ。

解答：

13 ÷ 2 = 6 余り 1
 6 ÷ 2 = 3 余り 0
 3 ÷ 2 = 1 余り 1
 1 ÷ 2 = 0 余り 1

余りを逆順に並べると：$1101_{(2)}$ （例題4と一致）

5.5. 例題6：16進法 ↔ 2進法の変換

問題： $A3_{(16)}$ を2進法で表せ。（A = 10）

解答：

16進法の各桁を4ビットの2進法に変換：

• $$A = 10 = 1010_{(2)}$$
• $$3 = 0011_{(2)}$$

$$A3_{(16)} = 10100011_{(2)}$$

---

6. n進法の計算

n進法のまま足し算・引き算を行うこともできます。

2進法の足し算： $1101_{(2)} + 0110_{(2)}$

  1101
+ 0110
------
 10011

$= 10011_{(2)} = 16 + 2 + 1 = 19$ （検証：$13 + 6 = 19$ ✓）

---

7. まとめ

ユークリッドの互除法の詳細は ユークリッドの互除法 を、素因数分解と GCD の基礎は 約数・倍数・素因数分解 を参照してください。

---

8. クイズ

問1. $4x + 9y = 1$ の整数解をすべて求めよ。

正解： $x = -2 + 9t$、$y = 1 - 4t$（$t \in \mathbb{Z}$）

解説： $4(-2) + 9(1) = -8 + 9 = 1$ より特殊解 $(-2, 1)$。一般解は $x = -2 + 9t$、$y = 1 - 4t$。

問2. $10111_{(2)}$ を10進法に変換せよ。

正解： $23$

解説： $1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 16 + 0 + 4 + 2 + 1 = 23$

問3. 25を3進法で表せ。

正解： $221_{(3)}$

解説： $25 \div 3 = 8$ 余り $1$、$8 \div 3 = 2$ 余り $2$、$2 \div 3 = 0$ 余り $2$。余りを逆順に並べると $221_{(3)}$。確認：$2 \times 9 + 2 \times 3 + 1 = 18 + 6 + 1 = 25$ ✓