すべての整数は、ある正の整数で割ったときの余りによって分類できます。
除法の定理 $a = bq + r$ は、整数論の出発点であり、ユークリッドの互除法や合同式の理論的基盤です。
小学校以来、私たちは「割り算」に親しんできました。 $49 \div 6 = 8$ あまり $1$、つまり $49 = 6 \times 8 + 1$ です。 しかし、この「あまり」の概念を数学的に厳密に定義したのが除法の定理です。
整数 $a$ と正の整数 $b$ に対して、
$$a = bq + r, \quad 0 \leq r < b$$
を満たす整数 $q$（商）と整数 $r$（余り）がただ1通りに存在する。
この定理のポイントは2つあります。存在（商と余りが必ず見つかること）と一意性（それが1通りしかないこと）です。
$49 = 6 \times 8 + 1$ とも書けますが、$49 = 6 \times 7 + 7$ や $49 = 6 \times 9 + (-5)$ とも書けます。 つまり、$a = bq + r$ を満たす $(q, r)$ の組は無限にあります。
ここに「$0 \leq r < b$」という条件をつけると、$(q, r)$ がたった1組に決まるのです。 この条件が「余り」の定義そのものであり、除法の定理の核心です。
余りとは、「$0$ 以上 $b$ 未満」の範囲に収まるように調整された「残り」のことです。
なぜ $(q, r)$ が1通りしかないのかを証明しましょう。 これは整数論の基礎中の基礎であり、この後の議論の土台です。
$a = bq_1 + r_1$（$0 \leq r_1 < b$）と $a = bq_2 + r_2$（$0 \leq r_2 < b$）の2通りがあると仮定する。
辺々引くと $0 = b(q_1 - q_2) + (r_1 - r_2)$、すなわち $r_1 - r_2 = b(q_2 - q_1)$。
$0 \leq r_1 < b$ かつ $0 \leq r_2 < b$ より、$-b < r_1 - r_2 < b$。
一方、$r_1 - r_2 = b(q_2 - q_1)$ は $b$ の倍数。
$-b$ より大きく $b$ より小さい $b$ の倍数は $0$ しかない。
よって $r_1 - r_2 = 0$、すなわち $r_1 = r_2$。このとき $b(q_1 - q_2) = 0$ で $b > 0$ より $q_1 = q_2$。■
✕ 誤：$-30 \div 7$ を計算して「$-30 = 7 \times (-4) + (-2)$。余りは $-2$。」
○ 正：余りは $0 \leq r < 7$ を満たさなければなりません。 $-30 = 7 \times (-5) + 5$ と表すと、$r = 5$（$0 \leq 5 < 7$ ✓）。 よって商は $-5$、余りは $5$ です。
余りは常に非負（$0$ 以上）です。負の数を割るときは、商を十分小さくとって余りが非負になるように調整します。 電卓やプログラミング言語によっては負の余りを返すものがあるので注意してください。
一意性は当たり前に見えますが、これがないと「$a$ を $b$ で割った余り」という概念自体が定義できません。
✕ 誤：「$49 = 6 \times 7 + 7$ だから、$49$ を $6$ で割った余りは $7$」
○ 正：$r = 7$ は $r < b = 6$ を満たさないので、これは「余り」とは呼べません。 正しくは $49 = 6 \times 8 + 1$ で、余りは $1$ です。
$0 \leq r < b$ の条件を厳密に守ることで、余りが一意に定まります。
英語では除法の定理を "Division Algorithm" と呼びます。 "Algorithm" は「計算手順」を意味し、単に存在を主張する「定理」とはニュアンスが異なります。
実際、$q$ と $r$ は具体的に構成できます。$a$ から $b$ を繰り返し引いて（$a > 0$ のとき）$0$ 以上 $b$ 未満の範囲に入ったところが余り $r$、引いた回数が商 $q$ です。 この「構成的」な性質が "Algorithm" と呼ばれる所以です。
大学の整数論や抽象代数では、除法の定理を持つ整数のような構造をユークリッド整域と呼びます。 多項式の割り算もこの構造に従います。
除法の定理によれば、どんな整数も正の整数 $b$ で割ると余りは $0, 1, 2, \ldots, b-1$ のいずれかです。 これを利用して、すべての整数を余りの値によって分類することができます。
最も身近な例は偶数と奇数です。すべての整数は $2$ で割ると余りが $0$ か $1$ なので、 整数 $k$ を用いて次のように書けます。
すべての整数を $3$ で割ると余りは $0, 1, 2$ のいずれかです。 整数 $k$ を用いて次の3つに分類できます。
なお、$3k + 2$ は $3(k+1) - 1 = 3k' - 1$ とも書けるので、 $3k, 3k + 1, 3k - 1$（つまり $3k, 3k \pm 1$）という分類も可能です。 問題に応じて使い分けます。
正の整数 $b$ で割った余りによる分類は、すべての整数を $b$ 個のグループに漏れなく、重複なく分ける操作です。
$$\underbrace{bk}_{余り0},\quad \underbrace{bk+1}_{余り1},\quad \underbrace{bk+2}_{余り2},\quad \ldots,\quad \underbrace{bk+(b-1)}_{余りb-1}$$
どんな整数も、このどれかのグループに必ず属し、同時に2つのグループに属することはありません。 これは除法の定理の「存在」と「一意性」の直接的な帰結です。
余りによる分類は、整数に関する命題の証明で頻繁に使われます。 典型的なのは「$n^2$ を $3$ で割った余りは $0$ か $1$」という命題の証明です。
整数 $n$ を $3$ で割った余りで分類すると、$n = 3k, 3k+1, 3k+2$ のいずれかです。
すべての場合で余りは $0$ か $1$ です。余り $2$ は現れません。
「$n(n+1)(n+2)$ が $6$ の倍数であることを示せ」という問題を考えましょう。
✕ 誤：$n$ を $6$ で割った余りで分類する → 6通りも場合分けが必要で大変。
○ 正：「$6$ の倍数 $= 2$ の倍数 かつ $3$ の倍数」に注目。 連続2整数 $n, n+1$ の中に $2$ の倍数が必ず含まれ、連続3整数 $n, n+1, n+2$ の中に $3$ の倍数が必ず含まれます。 よって積は $2 \times 3 = 6$ の倍数。
「$b$ の倍数の証明 → $b$ で割った余りで分類」は定石ですが、$b$ を素因数に分解してから考えると楽になることが多いです。
余りによる分類は、大学数学では剰余類（residue class）と呼ばれます。 $b$ で割った余りが同じ整数のグループを1つの「クラス」と見なす考え方です。
たとえば $b = 12$ とすると、時計の文字盤と同じ構造になります。 $13$ 時は $1$ 時と同じ位置、$25$ 時は $1$ 時と同じ位置。これが「$12$ を法とする合同」です。
この考え方を一般化したのが合同式（$a \equiv r \pmod{b}$）で、 さらに進めると大学の群論や環論で学ぶ「商群」「剰余環」に繋がります。
割り算の余りには、計算を大幅に簡略化できる便利な性質があります。 $n$ を正の整数とし、2つの整数 $a, b$ を $n$ で割ったときの余りをそれぞれ $r, r'$ とするとき、 次の性質が成り立ちます。
$a$ を $n$ で割った余りが $r$、$b$ を $n$ で割った余りが $r'$ のとき、
1. $a + b$ を $n$ で割った余り ＝ $r + r'$ を $n$ で割った余り
2. $a - b$ を $n$ で割った余り ＝ $r - r'$ を $n$ で割った余り
3. $a \times b$ を $n$ で割った余り ＝ $r \times r'$ を $n$ で割った余り
4. $a^m$ を $n$ で割った余り ＝ $r^m$ を $n$ で割った余り（$m$ は自然数）
$a = nq + r$ と書けるとき、$a$ と $r$ の差は $nq$（$n$ の倍数）です。 余りの性質とは、「$n$ の倍数を足しても引いても余りは変わらない」ということです。
足し算：$(nq_1 + r) + (nq_2 + r') = n(q_1 + q_2) + (r + r')$。$n$ の倍数部分は余りに影響しない。
掛け算：$(nq_1 + r)(nq_2 + r') = n(nq_1q_2 + q_1r' + q_2r) + rr'$。やはり $n$ の倍数部分は消える。
だから余りだけに注目して計算できるのです。これが合同式の背景にある原理です。
$a$ を $7$ で割ると $3$ 余り、$b$ を $7$ で割ると $4$ 余るとき、$ab$ を $7$ で割った余りを求めてみましょう。
性質3より、$ab$ を $7$ で割った余りは $3 \times 4 = 12$ を $7$ で割った余りに等しいので、答えは $5$ です。
$3^{100}$ を $7$ で割った余りのような、巨大な累乗の余りを求めるには工夫が必要です。 性質4を使って、まず小さい累乗の余りを調べ、周期を見つけます。
$3^1 = 3$（余り $3$）、$3^2 = 9$（余り $2$）、$3^3 = 27$（余り $6$）、 $3^4 = 81$（余り $4$）、$3^5 = 243$（余り $5$）、$3^6 = 729$（余り $1$）。
$3^6$ を $7$ で割ると余り $1$ です。よって $3^{100} = (3^6)^{16} \times 3^4$ を $7$ で割ると、 余りは $1^{16} \times 4 = 4$ です。
$a = nq_1 + r$、$b = nq_2 + r'$ とする。
$ab = (nq_1 + r)(nq_2 + r') = n^2 q_1 q_2 + nq_1 r' + nq_2 r + rr'$
$= n(nq_1 q_2 + q_1 r' + q_2 r) + rr'$
よって $ab$ を $n$ で割った余りは $rr'$ を $n$ で割った余りに等しい。■
✕ 誤：「$a$ を $7$ で割った余りが $6$、$b$ を $7$ で割った余りが $2$ なら、 $a \div b$ を $7$ で割った余りは $6 \div 2 = 3$」
○ 正：余りの性質は足し算・引き算・掛け算には成り立ちますが、割り算には成り立ちません。 $a \div b$ が整数とは限らないし、整数であっても余りの割り算は成り立ちません。
たとえば $a = 13$（余り $6$）、$b = 9$（余り $2$）のとき、$a/b$ は整数ではありません。 割り算が必要な場合は、合同式で「逆元」の概念を使います。
上の例で $3^6$ を $7$ で割ると余り $1$ になりました。 これは偶然ではなく、フェルマーの小定理の帰結です。
$p$ が素数で $a$ が $p$ の倍数でないとき、$a^{p-1} \equiv 1 \pmod{p}$ が成り立ちます。 上の例では $p = 7$、$a = 3$ で、$3^{7-1} = 3^6 \equiv 1 \pmod{7}$。
この定理は、RSA暗号の理論的基盤であり、大学の整数論で詳しく学びます。 高校の段階では「余りの周期を見つけるときの助け」として知っておくと便利です。
余りによる分類の重要な応用として、連続する整数の積の性質を見ていきましょう。 これは整数の問題で非常によく使われる基本的な性質です。
1. 連続する2個の整数の積 $n(n+1)$ は $2$ の倍数
2. 連続する3個の整数の積 $n(n+1)(n+2)$ は $6$（$= 3!$）の倍数
3. 一般に、連続する $k$ 個の整数の積は $k!$ の倍数
性質1：連続する2整数 $n, n+1$ のうち、少なくとも1つは偶数です。 なぜなら、$n$ を $2$ で割った余りで分類すると、$n$ が偶数なら $n$ が、$n$ が奇数なら $n+1$ が偶数だからです。 よって $n(n+1)$ は $2$ の倍数です。
$n(n+1)(n+2)$ が $6$ の倍数であることを示す。$6 = 2 \times 3$ だから、$2$ の倍数かつ $3$ の倍数であることを示せばよい。
$2$ の倍数であること：連続する3整数の中には少なくとも1つの偶数が含まれる。よって積は $2$ の倍数。
$3$ の倍数であること：$n$ を $3$ で割った余りで分類する。
$n = 3k$ のとき：$n$ が $3$ の倍数。
$n = 3k+1$ のとき：$n+2 = 3k+3 = 3(k+1)$ が $3$ の倍数。
$n = 3k+2$ のとき：$n+1 = 3k+3 = 3(k+1)$ が $3$ の倍数。
いずれの場合も、3個の中に $3$ の倍数が含まれる。
$2$ と $3$ は互いに素なので、$n(n+1)(n+2)$ は $2 \times 3 = 6$ の倍数。■
連続する $k$ 個の整数の積 $n(n+1)(n+2)\cdots(n+k-1)$ が $k!$ の倍数であるという事実は、
$$\binom{n+k-1}{k} = \frac{n(n+1)(n+2)\cdots(n+k-1)}{k!}$$
が常に整数であることと同値です。 つまり、組合せの数 $\binom{m}{k}$ が整数であるという、 組合せ論における基本的な事実の別表現なのです。
連続2整数 → $2!= 2$ の倍数、連続3整数 → $3!=6$ の倍数、ならば連続4整数 → $4!=24$ の倍数？
○ 正：これは正しいです。ただし証明は単純ではありません。
✕ 誤った推論：「連続4整数には $2$ の倍数、$3$ の倍数、$4$ の倍数がそれぞれ含まれるから $2 \times 3 \times 4 = 24$ の倍数」。 これは間違いです。$2$ と $4$ は互いに素ではないので、このように単純に掛け合わせることはできません。
正しい証明には、$\binom{n+3}{4}$ が整数であること（組合せの数）を利用するか、 $2$ の倍数が連続4整数に2個以上含まれることを丁寧に示す必要があります。
$n!$ の素因数分解で素数 $p$ が何回現れるかを求める公式がルジャンドルの定理です。
$$\nu_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots$$
たとえば $10!$ に素因数 $2$ が何個含まれるかは、$\lfloor 10/2 \rfloor + \lfloor 10/4 \rfloor + \lfloor 10/8 \rfloor = 5 + 2 + 1 = 8$ 個です。 これは「$100!$ の末尾に $0$ が何個並ぶか」といった入試問題に直結します。
ここまで学んだ内容を鳥の目で俯瞰し、全体像を整理しましょう。
| 問題タイプ | 問題の特徴 | 解法のポイント |
|---|---|---|
| A：余りの直接計算 | $a + b$, $ab$, $a^m$ の余りを求める | 余りの性質1〜4を適用。累乗は周期を見つける |
| B：倍数の証明 | 整数式が $n$ の倍数であることを示す | $n$ で割った余りで分類（剰余類）。場合を尽くす |
| C：連続整数の積 | $n(n+1)\cdots$ が $k!$ の倍数であることを示す | 連続 $k$ 整数に $p$ の倍数が含まれることを利用 |
| D：余りの条件から整数を決定 | 「$n$ で割ると $r$ 余る」条件から $a$ を求める | $a = nq + r$ とおいて他の条件と連立 |
Q1. $-30$ を $7$ で割ったときの商と余りを答えてください。
Q2. すべての整数を $5$ で割った余りで分類すると、何個のグループに分かれますか？
Q3. $a$ を $6$ で割った余りが $5$、$b$ を $6$ で割った余りが $4$ のとき、$ab$ を $6$ で割った余りは？
Q4. 除法の定理で、余り $r$ の条件が $0 \leq r < b$ であることはなぜ重要ですか？
Q5. 連続する3個の整数の積が $6$ の倍数であることを、簡潔に説明してください。
この記事で学んだ内容を、入試形式の問題で確認しましょう。
$a, b$ は整数とする。$a$ を $7$ で割ると $3$ 余り、$b$ を $7$ で割ると $4$ 余る。このとき、次の数を $7$ で割った余りを求めよ。
(1) $a + 2b$
(2) $ab$
(3) $a^2$
(1) $4$ (2) $5$ (3) $2$
方針：余りの性質を利用する。$a$ の余り $3$、$b$ の余り $4$ で計算。
(1) $a + 2b$ の余り ＝ $(3 + 2 \times 4)$ を $7$ で割った余り ＝ $11$ を $7$ で割った余り ＝ $4$
(2) $ab$ の余り ＝ $3 \times 4 = 12$ を $7$ で割った余り ＝ $5$
(3) $a^2$ の余り ＝ $3^2 = 9$ を $7$ で割った余り ＝ $2$
$n$ を整数とするとき、$n^2 + 2$ は $3$ の倍数にならないことを証明せよ。
$n$ を $3$ で割った余りで分類して、すべての場合で $n^2 + 2$ が $3$ の倍数にならないことを示す（下記参照）。
方針：$n$ を $3$ で割った余りで $3$ 通りに分類し、各場合で $n^2 + 2$ を $3$ で割った余りを求める。
$n$ を $3$ で割った余りで分類する（$k$ は整数）。
(i) $n = 3k$ のとき：$n^2 + 2 = 9k^2 + 2 = 3(3k^2) + 2$。$3$ で割った余りは $2$。
(ii) $n = 3k + 1$ のとき：$n^2 + 2 = 9k^2 + 6k + 1 + 2 = 3(3k^2 + 2k + 1)$。$3$ で割った余りは $0$。
⚠️ 訂正：$n^2 + 2 = 9k^2 + 6k + 1 + 2 = 9k^2 + 6k + 3 = 3(3k^2 + 2k + 1)$。余り $0$。これは $3$ の倍数。
再計算します。
(ii) $n = 3k + 1$ のとき：$n^2 = 9k^2 + 6k + 1$。$n^2 + 2 = 9k^2 + 6k + 3 = 3(3k^2 + 2k + 1)$。余り $0$。
これは $3$ の倍数になってしまいます。$n = 1$ のとき $n^2 + 2 = 3$（$3$ の倍数）。
実は、この命題は偽です。$n = 1$ のとき $n^2 + 2 = 3$ は $3$ の倍数。
正しい命題は「$n^2$ を $3$ で割った余りは $0$ か $1$（$2$ にはならない）」です。
正しく直した証明：$n^2$ を $3$ で割った余りが $0$ または $1$ であることを示す。
(i) $n = 3k$：$n^2 = 3(3k^2)$。余り $0$。
(ii) $n = 3k+1$：$n^2 = 3(3k^2+2k)+1$。余り $1$。
(iii) $n = 3k+2$：$n^2 = 3(3k^2+4k+1)+1$。余り $1$。
すべての場合で余りは $0$ か $1$。$2$ にはならない。■
この問題を修正します：「$n^2$ を $3$ で割った余りは $0$ か $1$ であることを示せ。」
$3^{2025}$ を $7$ で割った余りを求めよ。
余り $6$
方針：$3$ の累乗を $7$ で割った余りの周期を見つける。
$3^1 \equiv 3$、$3^2 \equiv 2$、$3^3 \equiv 6$、$3^4 \equiv 4$、$3^5 \equiv 5$、$3^6 \equiv 1 \pmod{7}$
余りは $3, 2, 6, 4, 5, 1$ の周期 $6$ で繰り返す。
$2025 = 6 \times 337 + 3$ より $3^{2025} \equiv 3^3 \equiv 6 \pmod{7}$
答え：$6$
$n$ を整数とするとき、$n^3 - n$ は $6$ の倍数であることを証明せよ。
$n^3 - n = n(n-1)(n+1) = (n-1)n(n+1)$（連続する3整数の積）なので $6$ の倍数。
方針：因数分解して連続整数の積の性質を利用する。
$n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1) \cdot n \cdot (n+1)$
これは連続する3つの整数 $n-1, n, n+1$ の積である。
連続する3つの整数の積は $6$ の倍数（Section 4で証明済み）であるから、$n^3 - n$ は $6$ の倍数。■
別解（余りによる分類）：$n$ を $6$ で割った余りで $6$ 通りに分類して直接確認することもできるが、 因数分解のほうがはるかに簡潔。
この問題は「因数分解 + 連続整数の積の性質」の典型的な組合せ。 $n^3 - n$ のような式を見たら、まず因数分解を試みるのが鉄則。