整数の証明と求値の6つの型 — 余り・連続積・互いに素・約数・有界・鳩の巣

文: KOSNiZ·最終更新: 2026年9月6日

整数の問題は、計算量が少ないのに、「何から手を付けるか」で止まります。整数には、実数にはない「離散性」(隣の整数との間に何もない)と「約数・倍数の構造」があり、それを使う論法は数種類に決まっています。この記事では、整数の証明と求値の型を6つに分け、それぞれの目印と書き方を説明します。

型1: 余りで分類する

「すべての整数 $n$ について〜」という主張は、 $n$ を余りで分類して場合ごとに確かめます。3で割った余りなら $3 k$ 、 $3 k + 1$ 、 $3 k + 2$ の3通りです。「何で割った余りで分けるか」は、問題に出てくる数(6の倍数なら2と3、8の倍数なら8、平方数なら4か8)が目安です。

平方数を4で割った余りは0か1だけ、3で割った余りも0か1だけ、という事実は、この型で繰り返し使います。「 $x^{2} + y^{2} = 3$ に整数解がない」のような「存在しない」証明は、余りの制約で否定します。整数の性質の基礎「余りによる整数の分類」、標準「平方数を4で割った余り」、応用「整数解をもたないことの証明」の順に進んでください。

型2: 連続する整数の積

$n (n + 1)$ は2の倍数、 $n (n + 1) (n + 2)$ は6の倍数です。連続する $k$ 個の整数には、必ず $k$ の倍数が含まれるからです。「 $n^{3} - n$ が6の倍数」は、 $(n - 1) n (n + 1)$ と因数分解すればこの型です。目印は、因数分解すると連続する整数の積が現れることです。基礎「連続する整数の積」と標準「n³−n が6の倍数であること」で確認してください。

型3: 互いに素を使う

「 $a$ と $b$ が互いに素で、 $a$ が $b c$ を割り切るなら、 $a$ は $c$ を割り切る」という性質が、この型の要です。1次不定方程式 $a x + b y = c$ の一般解は、 $a (x - x_{0}) = - b (y - y_{0})$ の形にして、 $a$ と $b$ が互いに素だから $x - x_{0}$ が $b$ の倍数、という論法で求まります。基礎「1次不定方程式の整数解」、標準「一般解」「連続する整数が互いに素であること」で、この論法の書き方を固めてください。 $2$ が無理数であることの証明(数学Iの集合と命題)も、 $p$ と $q$ が互いに素という仮定に矛盾を導く、この型です。

型4: 積の形にして約数を数える

$x y = 12$ のような「積 = 定数」の形の整数方程式は、右辺の約数の組を全部書き出せば解けます。 $x y + 2 x + 3 y = 5$ のような形は、 $(x + 3) (y + 2) = 11$ と因数分解して積の形にします(「たすき」に定数を足す変形)。目印は、2文字の整数方程式で、次数が低いことです。基礎「分数が整数になる条件」、標準「分数が整数になる整数」、難関の整数解をもたないことの証明(無限降下)で確認してください。

約数の個数・総和は、素因数分解 $p^{a} q^{b}$ から $(a + 1) (b + 1)$ で数えます。「約数がちょうど15個の最小の整数」のような逆算は、 $15 = 3 \times 5 = 15 \times 1$ の分解から指数の組を決めます(難関の同名の問題)。

型5: 大小で挟む(有界性)

「 $x \leq y \leq z$ で $\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1$ を満たす自然数の組」のような問題は、大小の仮定から $x$ の範囲を絞り( $\frac{3}{x} \geq 1$ から $x \leq 3$ )、 $x$ を1つずつ試します。目印は、対称な整数方程式で、解が有限個と予想されることです。最難関編の単位分数の和 1/2 への分解がこの型です。「整数だから範囲が絞れれば有限個」という離散性が、この型の根拠です。

型6: 鳩の巣原理

「 $n + 1$ 個のものを $n$ 個の箱に入れると、2個以上入る箱がある」という原理で、「必ず〜が存在する」型の証明に使います。「51個の数から割り切る対がある」「連続する和が $n$ の倍数になる」といった問題で、「余りで分類した箱に、個数より多いものを入れる」という形で使います。数学Iの集合と命題の実戦編「51個の数から割り切る対がある」と、整数の性質の実戦編「連続する和が n の倍数」で確認してください。

答案で必ず書くこと

整数の証明では、「余りで分類する」と宣言してから場合を全部並べ、「すべての場合で成り立つ」と締めます。表にすると漏れが見えます。「互いに素」を使うときは、なぜ互いに素なのか(問題の仮定か、連続する整数だからか)を1行書きます。「存在しない」の証明では、背理法か、余りの制約かを最初に宣言します。証明の型の全体は証明問題の5つの型にまとめてあります。

つまずきやすいところ

最も多い誤りは、余りによる分類で場合が漏れることです。表に全部書いて、「以上より」で締めてください。次に、「互いに素」の性質を、互いに素でないときにも使ってしまうことです。3つ目は、不定方程式の一般解で、パラメータの範囲(自然数解なら正になる範囲)を求め忘れることです。