入試の整数問題は、約数・倍数、ユークリッドの互除法、不定方程式、証明が複合的に絡み合います。
この記事では、第9章の知識を総動員して総合問題に挑む力を身につけます。
9-2で学んだ不定方程式の解法を、実際の応用問題に展開します。 不定方程式は「整数解の候補が無限にある」状態から、 追加の条件（正の整数、範囲の制限など）を使って有限個に絞り込む問題です。
不定方程式 $ax + by = c$ の一般解は $x = x_0 + bt$、$y = y_0 - at$（$t$ は整数）の形です。 ここまでは機械的に求まりますが、応用問題では追加条件による絞り込みが本番です。
「$x > 0$ かつ $y > 0$」という条件から $t$ の範囲を不等式で求め、 整数 $t$ の個数が答えに直結します。 不定方程式を解くことがゴールではなく、条件に合う解を数えることがゴールです。
「50円硬貨と80円硬貨を合わせてちょうど1000円を支払う方法は何通りあるか」 という問題を考えましょう。$50x + 80y = 1000$（$x \geq 0, y \geq 0$, 整数）を解きます。
Step 1：両辺を10で割って簡約化。$5x + 8y = 100$
Step 2：特殊解を見つける。$x = 4, y = 10$ は解（$5 \times 4 + 8 \times 10 = 100$）。
Step 3：一般解を求める。$5(x - 4) + 8(y - 10) = 0$ より $5(x - 4) = -8(y - 10)$。
5と8は互いに素なので、$x - 4 = 8t$、$y - 10 = -5t$（$t$ は整数）。
$$x = 4 + 8t, \quad y = 10 - 5t$$
Step 4：$x \geq 0$ かつ $y \geq 0$ から $t$ の範囲を求める。
$4 + 8t \geq 0 \Rightarrow t \geq -\frac{1}{2}$、$10 - 5t \geq 0 \Rightarrow t \leq 2$
$t$ は整数なので $t = 0, 1, 2$。3通り。
$(x, y) = (4, 10), (12, 5), (20, 0)$
問題文が「何通りの支払い方があるか」なら、0枚の場合も含むので $x \geq 0, y \geq 0$。 「少なくとも1枚ずつ使う」なら $x \geq 1, y \geq 1$。
✕ 誤：条件を確認せずに $x > 0, y > 0$ と決めつけ、解を1つ見落とす
○ 正：問題文の条件を正確に読み取り、不等式に反映する
上の例で「両方の硬貨を使う」条件なら $t = 0, 1$ の2通りになります。
不定方程式の別の応用として、積の形に変形して約数の組を調べる手法があります。 たとえば $xy + 2x + 3y = 20$ は次のように解けます。
左辺に $6$ を足すと $xy + 2x + 3y + 6 = 26$、つまり $(x+3)(y+2) = 26$。 $26 = 1 \times 26 = 2 \times 13$ と因数分解して、$x+3, y+2$ の組を調べれば答えが出ます。
整数の不定方程式は、「$AB = N$（$N$ は定数）」の形に持ち込めれば一気に解けます。 $N$ の約数の組 $(A, B)$ を列挙するだけで、すべての整数解が求まるからです。
この「積の形への変形」こそが、入試の不定方程式で最も頻出のテクニックです。 $xy + ax + by = c$ の形を見たら、$(x+b)(y+a) = c + ab$ の変形を試みましょう。
$(x+3)(y+2) = 26$ を解くとき、$x, y$ が正の整数、0以上の整数、任意の整数のどれかで答えが変わります。
✕ 誤：$x, y$ が正の整数なのに、$(x+3, y+2) = (1, 26)$ つまり $x = -2$ を含めてしまう
○ 正：$x, y$ が正の整数なら $x+3 \geq 4, y+2 \geq 3$。 $26 = 2 \times 13$ で $x+3 = 13, y+2 = 2$ → $x = 10, y = 0$ は $y > 0$ を満たさない。 条件を満たす解がない場合もある
整数問題で最も多いミスは、問題文の整数条件を最後まで意識し続けないことです。
整数解を求める方程式は、古代ギリシャの数学者ディオファントスにちなんで ディオファントス方程式と呼ばれます。高校で扱うのは1次と2次の場合ですが、 一般の $n$ 次方程式の整数解の存在判定は極めて難しい問題です。
特に有名なのがフェルマーの最終定理「$n \geq 3$ のとき $x^n + y^n = z^n$ は自明でない整数解をもたない」で、 1637年の予想から1995年のワイルズによる証明まで約360年かかりました。
整数の性質は、図形の問題にも登場します。 「三角形の3辺がすべて整数」「直角三角形で辺が整数（ピタゴラス数）」 など、図形に整数条件が加わると、整数論の道具が必要になります。
整数と図形の融合問題のポイントは、図形の条件（面積、三平方の定理など）を 整数の方程式に翻訳することです。翻訳さえできれば、あとは不定方程式の解法が使えます。
たとえば「面積が整数の直角三角形で、直角を挟む2辺が整数」という問題は、 $\frac{1}{2}ab = S$（$a, b, S$ は正の整数）すなわち $ab = 2S$ という整数の問題になります。
ピタゴラス数とは、$a^2 + b^2 = c^2$ を満たす正の整数の組 $(a, b, c)$ のことです。 $(3, 4, 5)$、$(5, 12, 13)$、$(8, 15, 17)$ などが代表例です。
9-9で学んだ偶奇の議論を使うと、ピタゴラス数の重要な性質がわかります。 互いに素なピタゴラス数 $(a, b, c)$ では、$a, b$ のうち一方が偶数、他方が奇数で、$c$ は必ず奇数です。
互いに素で $a$ が偶数のピタゴラス数 $(a, b, c)$ は、次の公式ですべて生成できます。
$$a = 2mn, \quad b = m^2 - n^2, \quad c = m^2 + n^2$$
ただし $m > n > 0$、$\gcd(m, n) = 1$、$m$ と $n$ の偶奇が異なる。
検証：$a^2 + b^2 = 4m^2n^2 + m^4 - 2m^2n^2 + n^4 = m^4 + 2m^2n^2 + n^4 = (m^2 + n^2)^2 = c^2$ ✓
$m = 2, n = 1$ → $(a, b, c) = (4, 3, 5)$、$m = 3, n = 2$ → $(a, b, c) = (12, 5, 13)$
整数と図形の融合問題で、辺の長さを求めたら三角形の成立条件を必ず確認しましょう。
✕ 誤：$a^2 + b^2 = c^2$ を満たす正の整数の組を求めた → そのまま答える
○ 正：三角不等式 $a + b > c$、$b + c > a$、$c + a > b$ を確認する （ピタゴラス数なら $c$ が最大なので $a + b > c$ のみ確認すればよい）
ピタゴラス数では三角不等式は自動的に満たされますが、 一般の整数辺の三角形では必ず確認が必要です。
座標が整数である点を格子点と呼びます。 「単位円 $x^2 + y^2 = 1$ 上の有理点」と「ピタゴラス数」は密接に関連しています。 $\left(\frac{a}{c}, \frac{b}{c}\right)$ は単位円上の有理点になるからです。
整数論と幾何学の融合は、大学数学では数論幾何学という分野に発展します。 楕円曲線や代数幾何学の理論が暗号技術（楕円曲線暗号）にも応用されています。
整数の性質を確率の問題に応用する融合問題は、入試で頻出です。 典型的なのは「サイコロを振って得られる数の積・和に整数条件を課す」タイプの問題です。
たとえば「2個のサイコロの目の積が偶数になる確率」を求めるとき、 余事象（積が奇数になる確率）を考えると楽です。 積が奇数になるのは2つの目がともに奇数のときだけ。 奇数の目は $\{1, 3, 5\}$ の3つなので、$\frac{3}{6} \times \frac{3}{6} = \frac{1}{4}$。 よって積が偶数になる確率は $1 - \frac{1}{4} = \frac{3}{4}$。
整数と確率の融合問題では、1つ1つの場合を全部数えるのではなく、 整数の性質（偶奇、倍数、余り）で場合を分類してから数えるのがポイントです。
「積が3の倍数」→ 少なくとも一方が3の倍数。「和が偶数」→ 偶偶 or 奇奇。 整数の性質が「どの場合を数えるべきか」の指針を与えてくれます。
2個のサイコロの目の和が素数になる確率を考えましょう。 和の範囲は2〜12です。この中の素数は $2, 3, 5, 7, 11$ の5個。
各素数になる場合の数を直接数えます。和が2：$(1,1)$ の1通り。和が3：$(1,2), (2,1)$ の2通り。 和が5：$(1,4), (2,3), (3,2), (4,1)$ の4通り。和が7：$(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)$ の6通り。 和が11：$(5,6), (6,5)$ の2通り。合計 $1 + 2 + 4 + 6 + 2 = 15$ 通り。 確率は $\frac{15}{36} = \frac{5}{12}$。
✕ 誤：「和が素数」の問題で、和が1になる場合も含めてしまう（サイコロ2個の和は最小2なので実害はないが、一般の問題では注意）
○ 正：$1$ は素数ではない。素数は $2, 3, 5, 7, 11, 13, \ldots$ です
また、$2$ は唯一の偶数の素数です。「偶数の素数は存在しない」と勘違いしないようにしましょう。
パターン1：積の偶奇 積が偶数 ⇔ 少なくとも1つが偶数。余事象（すべて奇数）が楽
パターン2：和の偶奇 和が偶数 ⇔ 偶数同士 or 奇数同士。偶奇の組合せで分類
パターン3：倍数条件 積が $n$ の倍数 ⇔ 余りの積が $n$ の倍数。余りで分類して数える
パターン4：素数条件 直接列挙が基本。素数の一覧を正確に把握する
「$n$ 以下の整数からランダムに2つ選んだとき、互いに素である確率」は、 $n \to \infty$ で $\frac{6}{\pi^2} \approx 0.608$ に収束します。 これはリーマンゼータ関数 $\zeta(2) = \frac{\pi^2}{6}$ と関連する美しい結果です。
このように、整数の性質を確率的に分析する分野は確率的整数論と呼ばれ、 素数の分布や暗号の安全性評価などに応用されています。
入試で整数問題に出会ったとき、「何から手をつければよいかわからない」という声をよく聞きます。 ここでは、問題の特徴から解法を選ぶフローチャートを整理します。
整数問題は大きく分けて4つのタイプに分類できます。
A. 方程式型：「整数解を求めよ」→ 不定方程式の解法
B. 証明型：「〜を示せ」→ 場合分け・背理法・帰納法
C. 存在型：「〜が存在することを示せ」→ 構成的証明 or 背理法
D. 融合型：図形・確率などとの融合 → 条件を整数の式に翻訳してA〜Cに帰着
まず問題がどのタイプかを見極め、それに応じた戦略を選ぶのが第一歩です。
| タイプ | 見分け方 | まず試す手法 | 補助テクニック |
|---|---|---|---|
| A. 方程式型 | 「整数解を求めよ」「$n$ の値を求めよ」 | 積の形に変形 → 約数の列挙 | 互除法、mod で絞り込み |
| B. 証明型 | 「〜を示せ」「〜を証明せよ」 | 偶奇 or 余りで場合分け | 背理法、対偶、帰納法 |
| C. 存在型 | 「〜が存在するか」「少なくとも1つ」 | 具体例の構成（構成的証明） | 背理法、鳩ノ巣原理 |
| D. 融合型 | 図形・確率の問題に整数条件あり | 条件を整数の式に翻訳 | A〜Cのいずれかに帰着 |
方程式型の問題は、方程式の形によってさらに戦略が分かれます。
✕ 誤：「不定方程式だからユークリッドの互除法」と決めつけ、行き詰まる
○ 正：互除法がうまくいかなければ、積の形への変形や mod による絞り込みを試す
整数問題の特徴は、1つの問題に複数のアプローチが有効なこと。 1つの方法で行き詰まったら、別の角度から攻めましょう。 特に「mod で候補を減らす → 残りを直接確認」のコンビネーションは強力です。
1. 因数分解して「積 ＝ 定数」の形にできるか？ → Yes：約数の列挙で解く
2. 1次不定方程式 $ax + by = c$ の形か？ → Yes：互除法で一般解を求め、条件で絞る
3. $x^2$ など2乗を含むか？ → Yes：mod で候補を絞ってから探索
4. 分数型か？ → Yes：通分して整数の方程式に変換してから 1. に戻る
5. どれでもない → 文字を1つ固定して、もう一方の文字について解く。 「整数の範囲が有限になるように」不等式で絞り込む
整数問題を解く際の「mod で候補を絞ってから探索」という戦略は、 コンピュータサイエンスの探索アルゴリズムと同じ発想です。 探索空間（候補の数）をできるだけ小さくしてから全探索するのが効率的です。
暗号技術では、「大きな素数の積を因数分解する」ことの計算量的困難さが安全性の根拠です。 整数の性質を利用した効率的な探索は、数学だけでなく情報科学の核心でもあります。
第9章「整数の性質」で学んだ内容を振り返り、全体像を整理します。 各記事で学んだ概念がどのようにつながっているかを確認しましょう。
| 記事 | 中心テーマ | 主な道具 |
|---|---|---|
| 9-1 約数と倍数 | 整数の基本構造 | 約数・倍数の定義、素因数分解 |
| 9-2 互除法と不定方程式 | 最大公約数と方程式 | ユークリッドの互除法、1次不定方程式 |
| 9-3 整数の活用 | $n$ 進法、記数法 | 位取り記数法、$n$ 進法変換 |
| 9-9 整数の証明 | 証明手法 | 偶奇・余りの場合分け、背理法 |
| 9-10 総合問題 | 知識の統合 | 上記すべて＋図形・確率との融合 |
Q1. $xy + 2x + 3y = 20$ を正の整数の範囲で解くとき、最初にどのような変形をしますか？
Q2. 不定方程式 $3x + 5y = 47$ の一般解が $x = 4 + 5t$, $y = 7 - 3t$ のとき、$x > 0$ かつ $y > 0$ を満たす整数 $t$ の範囲は？
Q3. 2個のサイコロの目の積が3の倍数になる確率を、余事象を使って求めてください。
Q4. 整数問題の4つのタイプを挙げ、それぞれの特徴を一言で述べてください。
Q5. ピタゴラス数 $(a, b, c)$ で $a, b, c$ がすべて奇数になることはありません。なぜですか？
この記事で学んだ内容を、入試形式の問題で確認しましょう。
1個120円のりんごと1個200円のメロンを合わせてちょうど10個買い、代金の合計を1600円にしたい。 それぞれ何個ずつ買えばよいか。
りんご $x$ 個、メロン $y$ 個とすると、
$$x + y = 10 \quad \cdots ①$$
$$120x + 200y = 1600 \quad \cdots ②$$
①より $y = 10 - x$ を②に代入：$120x + 200(10 - x) = 1600$
$120x + 2000 - 200x = 1600$、$-80x = -400$、$x = 5$。$y = 5$。
りんご5個、メロン5個。
方針：2つの条件（個数の合計、金額の合計）から連立方程式を立てる。 変数が2つで方程式が2つなので、通常の連立方程式として解ける。 解が $x \geq 0, y \geq 0$ の整数であることを確認。
$\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{6}$ を満たす正の整数の組 $(x, y)$（$x \leq y$）をすべて求めよ。
$(x, y) = (7, 42), (8, 24), (9, 18), (10, 15), (12, 12)$
方針：通分して積の形に変形する。
$\frac{1}{x} + \frac{1}{y} = \frac{1}{6}$ の両辺に $6xy$ をかけると $6y + 6x = xy$。
$xy - 6x - 6y = 0$。両辺に36を足すと $(x-6)(y-6) = 36$。
$x \leq y$ より $x - 6 \leq y - 6$。また $x > 6$（$\frac{1}{x} < \frac{1}{6}$ だと $\frac{1}{x} + \frac{1}{y} < \frac{1}{6}$ に近づかないため。 正確には $x > 6$ は $\frac{1}{x} + \frac{1}{y} = \frac{1}{6}$、$y > 0$ より $\frac{1}{x} < \frac{1}{6}$、$x > 6$）。
$x - 6 \geq 1$ かつ $x - 6 \leq y - 6$。$(x-6)(y-6) = 36$ で、$x - 6$ は36の約数。
$36 = 1 \times 36 = 2 \times 18 = 3 \times 12 = 4 \times 9 = 6 \times 6$
$(x-6, y-6) = (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)$
$(x, y) = (7, 42), (8, 24), (9, 18), (10, 15), (12, 12)$
3個のサイコロを同時に振る。出た目の積が4の倍数になる確率を求めよ。
$\dfrac{5}{8}$
方針：余事象「積が4の倍数でない」を考える。 積が4の倍数でない ＝ 積を素因数分解したとき、2が高々1個しかない。
場合分け：
(i) 3つとも奇数：積に因数2がない → 4の倍数でない。 奇数の目は $\{1,3,5\}$ で3個。確率 $\left(\frac{3}{6}\right)^3 = \frac{1}{8}$
(ii) ちょうど1つが偶数で、その偶数が $2$ または $6$（つまり奇数×2の形）：
偶数の目 $\{2, 4, 6\}$ のうち、$2 = 2 \times 1$, $6 = 2 \times 3$ は2を1個だけ含み、$4 = 2^2$ は2を2個含む。
ちょうど1つが偶数で、それが $\{2, 6\}$ のとき、積は2を1個だけ含むので4の倍数でない。 3つのうち偶数の位置の選び方は $\binom{3}{1} = 3$ 通り。確率 $3 \times \frac{2}{6} \times \left(\frac{3}{6}\right)^2 = 3 \times \frac{1}{3} \times \frac{1}{4} = \frac{1}{4}$
余事象の確率：$\frac{1}{8} + \frac{1}{4} = \frac{3}{8}$
求める確率：$1 - \frac{3}{8} = \frac{5}{8}$
直角三角形の3辺の長さがすべて整数で、斜辺の長さが25であるとき、直角を挟む2辺の長さを求めよ。
$(a, b) = (7, 24)$ または $(15, 20)$（ただし $a < b$）
方針：$a^2 + b^2 = 625$（$a < b$, 正の整数）を満たす組を求める。
$a < b$ かつ $a^2 + b^2 = 625$ より、$a^2 < \frac{625}{2} = 312.5$、$a \leq 17$。
$b^2 = 625 - a^2$ が完全平方数になる $a$ を探す。
$a = 7$：$b^2 = 625 - 49 = 576 = 24^2$ ✓
$a = 15$：$b^2 = 625 - 225 = 400 = 20^2$ ✓
$a = 1 \sim 17$ の他の値では $625 - a^2$ が完全平方数にならない。
よって $(a, b) = (7, 24), (15, 20)$。
別解：$25 = 5^2$。ピタゴラス数の生成公式 $c = m^2 + n^2$ で $m^2 + n^2 = 25$。 $(m, n) = (3, 4)$ → $(a, b, c) = (24, 7, 25)$。 $(m, n) = (4, 3)$ → $(a, b, c) = (24, 7, 25)$（同じ）。
また $25 = 5 \times 5$ から、$(a, b, c) = (3, 4, 5)$ を5倍した $(15, 20, 25)$ も解。