整数問題 最強攻略法 mod活用術｜藤原進之介が徹底解説【日本数学塾・数強塾】

はじめに

こんにちは、日本数学塾・数強塾の看板講師、藤原進之介です。

今日は、大学受験数学において最も差がつく分野と言っても過言ではない「整数問題」について、その最強の武器「mod（合同式）」の活用術を徹底的に解説します。

正直に言います。整数問題は、多くの受験生が「何をすればいいかわからない」「方針が立たない」と悩む分野です。私も予備校講師として20年以上、数万人の受験生を指導してきましたが、整数問題で手が止まる生徒を何度も見てきました。

しかし、断言します。mod（合同式）を正しく理解し、使いこなせるようになれば、整数問題の8割以上は「得点源」に変わります。

特に東京大学・京都大学・一橋大学・東工大などの難関国公立大学や、早稲田・慶應・上智などの難関私立大学では、整数問題が頻出です。京都大学に至っては、整数問題の約5割以上がmod 3で解けるというデータもあるほどです。

この記事では、以下のことを約束します：

• modの基本概念を「なぜそうなるのか」から徹底理解
• 具体的な入試問題5問以上を詳細な解説付きで紹介
• 問題タイプ別の使い分けを完全マスター
• よくあるミスとその対処法を網羅
• 実践的な演習ステップで確実に実力アップ

この記事を読み終わる頃には、あなたは整数問題を見た瞬間に「どのmodを使えばいいか」が直感的にわかるようになっているでしょう。

さあ、一緒に整数問題の世界を征服しましょう！

【核心】整数問題 最強攻略法 mod活用術の要点

1. mod（合同式）とは何か？～本質を理解する～

まず、mod（モッド）とは何かを、根本から理解しましょう。

modとは、「割り算の余りだけに注目した数学的ツール」です。正式には「合同式」と呼ばれます。

【定義】合同式の意味

2つの整数 a と b があるとき、a と b を正の整数 m で割った余りが等しい場合、次のように書きます：

a ≡ b (mod m)

これを「a と b は法 m のもとで合同である」と読みます。

【具体例】

• 17 ≡ 5 (mod 4) ... 17÷4=4余り1、5÷4=1余り1 → 余りが同じ
• 23 ≡ 2 (mod 7) ... 23÷7=3余り2 → 2と合同
• 100 ≡ 1 (mod 9) ... 100÷9=11余り1

【なぜmodが強力なのか？】

ここで重要なのは、「なぜわざわざ余りに注目するのか」という本質です。

整数問題では、「〇〇で割り切れる」「〇〇の倍数である」「〇〇で割った余りを求めよ」という割り算に関する問題が非常に多いです。

通常、a = bq + r（商と余りの式）を使って計算すると、計算が複雑になりがちです。しかしmodを使えば、余りの計算だけに集中でき、計算が劇的に楽になります。

2. mod（合同式）の6つの基本性質

modを使いこなすには、以下の6つの基本性質を完璧に覚える必要があります。これらは全ての整数問題の土台となります。

【性質1】反射律

任意の整数 a について、a ≡ a (mod m)

【性質2】対称律

a ≡ b (mod m) ならば、b ≡ a (mod m)

【性質3】推移律

a ≡ b (mod m) かつ b ≡ c (mod m) ならば、a ≡ c (mod m)

【性質4】加法・減法の保存

a ≡ b (mod m) かつ c ≡ d (mod m) のとき、
a + c ≡ b + d (mod m)
a - c ≡ b - d (mod m)

【ポイント】合同式は辺々足し算・引き算ができる！

【性質5】乗法の保存

a ≡ b (mod m) かつ c ≡ d (mod m) のとき、
ac ≡ bd (mod m)

【ポイント】合同式は辺々かけ算ができる！これが超重要！

【性質6】累乗への拡張

a ≡ b (mod m) のとき、任意の正の整数 n について
a^n ≡ b^n (mod m)

【ポイント】これにより、巨大な累乗の余りも簡単に計算できる！

【注意】割り算は慎重に！

ab ≡ ac (mod m) だからといって、b ≡ c (mod m) とは限らない！
割り算ができるのは、a と m が互いに素のときだけ。

例：6 ≡ 12 (mod 6) だが、両辺を2で割って 3 ≡ 6 (mod 6) は成立しません。

3. modの法（何で割るか）の選び方

整数問題でmodを使う際、「何を法として選ぶか」が勝負を決めます。以下に、頻出の法とその使い所を整理します。

【mod 2】偶奇を見る

• 使う場面：偶数・奇数の判定、2の倍数の証明
• ポイント：整数は mod 2 で 0 か 1 のみ
• 例：n² の偶奇は n の偶奇と一致

【mod 3】3の倍数判定・京大の必須武器

• 使う場面：3の倍数の証明、n² + 1 の性質など
• ポイント：整数は mod 3 で 0, 1, 2 のいずれか
• 頻出事実：
  • n ≡ 0 (mod 3) → n² ≡ 0 (mod 3)
  • n ≡ 1 (mod 3) → n² ≡ 1 (mod 3)
  • n ≡ 2 (mod 3) → n² ≡ 1 (mod 3)

  つまり、平方数は mod 3 で 0 か 1 しか取らない！

【mod 4】平方数の性質

• 使う場面：平方数の問題、4の倍数判定
• 頻出事実：平方数は mod 4 で 0 か 1 しか取らない
  • 偶数 n = 2k → n² = 4k² ≡ 0 (mod 4)
  • 奇数 n = 2k+1 → n² = 4k² + 4k + 1 ≡ 1 (mod 4)

【mod 5】末尾の桁に関連

• 使う場面：5の倍数判定、末尾の数字に関する問題
• 頻出事実：
  • 10 ≡ 0 (mod 5) なので、10の累乗は全て 0
  • 平方数は mod 5 で 0, 1, 4 のみ

【mod 8】立方数・2のべき乗関連

• 使う場面：奇数の平方の性質、8の倍数判定
• 頻出事実：奇数の平方は mod 8 で必ず 1
  • (2k+1)² = 4k² + 4k + 1 = 4k(k+1) + 1
  • k(k+1) は連続する整数の積なので偶数
  • よって 4k(k+1) ≡ 0 (mod 8)、結果として (2k+1)² ≡ 1 (mod 8)

【mod 9】各位の和との関係

• 使う場面：各位の数字の和に関する問題
• 頻出事実：10 ≡ 1 (mod 9) より、自然数を mod 9 で考えると各位の和と等しくなる

4. フェルマーの小定理（上級テクニック）

難関大入試で必須となるフェルマーの小定理も押さえておきましょう。

【フェルマーの小定理】
p を素数、a を p の倍数でない整数とするとき、
a^(p-1) ≡ 1 (mod p)

【例】p = 7, a = 3 のとき

3^6 ≡ 1 (mod 7)

これを使えば、3^100 を 7 で割った余りも簡単に求められます：

3^100 = 3^(6×16+4) = (3^6)^16 × 3^4 ≡ 1^16 × 81 ≡ 81 ≡ 4 (mod 7)

5. 整数問題へのアプローチ総合戦略

modを使った整数問題の黄金戦略を伝授します：

1. 【Step 1】問題文を読み、何を示すべきか明確にする
2. 【Step 2】「余り」「倍数」「割り切れる」というキーワードを探す
3. 【Step 3】適切な法（mod の値）を選ぶ
   • 偶奇 → mod 2
   • 3の倍数 → mod 3
   • 平方数 → mod 4 または mod 3
   • 末尾 → mod 10
4. 【Step 4】変数を場合分けして全ての余りを検証
5. 【Step 5】矛盾を導くか、条件を絞り込む

具体的な問題例と解法（5問以上）

ここからは、実際の入試問題レベルの問題を取り上げ、modをどのように活用するかを詳細に解説します。

【問題1】基本：3^10 を 4 で割った余りを求めよ

【難易度】★☆☆☆☆（入門）

【出題傾向】定期テスト・共通テストレベル

【解法】

普通に 3^10 = 59049 を計算してから4で割るのは大変です。modを使いましょう。

mod 4 を考えます。

3 ≡ -1 (mod 4)

これがポイントです！3を「-1」と見ることで計算が一気に楽になります。

したがって、

3^10 ≡ (-1)^10 ≡ 1 (mod 4)

【答え】1

【ポイント解説】

mod 4 において 3 ≡ -1 と見る発想が重要です。負の数を使うと、累乗計算が劇的に楽になります。

• (-1)の偶数乗 → 1
• (-1)の奇数乗 → -1

【問題2】標準：n を整数とする。n² + 1 が 3 の倍数でないことを証明せよ

【難易度】★★☆☆☆（標準）

【出題傾向】中堅大学・センター試験・共通テストの応用

【解法】

mod 3 を考えます。

任意の整数 n は mod 3 で 0, 1, 2 のいずれかです。それぞれの場合について n² + 1 の値を調べます。

【場合1】n ≡ 0 (mod 3) のとき

n² ≡ 0² ≡ 0 (mod 3)

よって n² + 1 ≡ 0 + 1 ≡ 1 (mod 3) ≠ 0

【場合2】n ≡ 1 (mod 3) のとき

n² ≡ 1² ≡ 1 (mod 3)

よって n² + 1 ≡ 1 + 1 ≡ 2 (mod 3) ≠ 0

【場合3】n ≡ 2 (mod 3) のとき

n² ≡ 2² ≡ 4 ≡ 1 (mod 3)

よって n² + 1 ≡ 1 + 1 ≡ 2 (mod 3) ≠ 0

以上より、いずれの場合も n² + 1 ≡ 1 または 2 (mod 3) であり、0 にはならない。

したがって、n² + 1 は 3 の倍数ではない。（証明終わり）

【ポイント解説】

この問題の本質は、「平方数は mod 3 で 0 か 1 しか取らない」という事実です。

よって n² + 1 は mod 3 で 1 か 2 となり、0 にはなり得ません。この「平方数の余りパターン」は頻出なので必ず暗記しましょう！

【問題3】発展：2^345 を 30 で割った余りを求めよ（2021年 防衛医科大学校）

【難易度】★★★☆☆（発展）

【出題傾向】難関私立医大・国公立2次レベル

【解法】

30 = 2 × 3 × 5 と素因数分解できるので、中国剰余定理の考え方を使います。

つまり、mod 2, mod 3, mod 5 でそれぞれ余りを求め、最後に組み合わせます。

【Step 1】mod 2 で考える

2^345 は明らかに偶数なので、

2^345 ≡ 0 (mod 2)

【Step 2】mod 3 で考える

2 ≡ -1 (mod 3) より、

2^345 ≡ (-1)^345 ≡ -1 ≡ 2 (mod 3)

【Step 3】mod 5 で考える

フェルマーの小定理より、2^4 ≡ 1 (mod 5)

345 = 4 × 86 + 1 より、

2^345 = 2^(4×86+1) = (2^4)^86 × 2 ≡ 1^86 × 2 ≡ 2 (mod 5)

【Step 4】組み合わせる

求める余りを r とすると、

• r ≡ 0 (mod 2) → r は偶数
• r ≡ 2 (mod 3) → r = 3k + 2 の形
• r ≡ 2 (mod 5) → r = 5m + 2 の形

0 ≤ r < 30 の範囲で条件を満たす r を探します。

r ≡ 2 (mod 3) かつ r ≡ 2 (mod 5) より、r ≡ 2 (mod 15)

よって r = 2 または r = 17

さらに r ≡ 0 (mod 2)（偶数）より、r = 2

【答え】2

【ポイント解説】

法が合成数のとき、素因数に分解して個別に mod を取り、最後に組み合わせる手法は非常に強力です。中国剰余定理として知られていますが、入試では定理名を知らなくても解ける形で出題されることが多いです。

【問題4】難関：n³ - 7n + 9 が素数となる整数 n を全て求めよ（2018年 京都大学）

【難易度】★★★★☆（難関）

【出題傾向】京都大学頻出パターン・東大でも類題あり

【解法】

京都大学の整数問題といえば「mod 3」です。この問題も例に漏れません。

【Step 1】実験で仮説を立てる

まず、いくつかの整数で値を計算してみます：

n = -3, 1, 2 のとき素数（= 3）になりそうです。他の値では3の倍数で合成数になっています。

【Step 2】mod 3 で考える

f(n) = n³ - 7n + 9 とおきます。

-7 ≡ 2 (mod 3)、9 ≡ 0 (mod 3) より、

f(n) ≡ n³ + 2n (mod 3)

= n(n² + 2)

ここで mod 3 で場合分け：

【場合1】n ≡ 0 (mod 3) のとき

f(n) ≡ 0 × (0 + 2)

【問題4】続き

【場合1】n ≡ 0 (mod 3) のとき

f(n) ≡ 0 × (0 + 2) ≡ 0 (mod 3)

よって f(n) は3の倍数。

【場合2】n ≡ 1 (mod 3) のとき

f(n) ≡ 1 × (1 + 2) ≡ 1 × 3 ≡ 0 (mod 3)

よって f(n) は3の倍数。

【場合3】n ≡ 2 (mod 3) のとき

f(n) ≡ 2 × (4 + 2) ≡ 2 × 6 ≡ 2 × 0 ≡ 0 (mod 3)

よって f(n) は3の倍数。

重要な発見：n がどのような整数であっても、n³ - 7n + 9 は常に3の倍数です！

【Step 3】素数となる条件を絞る

f(n) が素数であるためには、f(n) が3の倍数でありかつ素数であること、つまり f(n) = 3 である必要があります。

よって、方程式 n³ - 7n + 9 = 3 を解きます。

n³ - 7n + 6 = 0

因数分解を試みます。n = 1 を代入すると、1 - 7 + 6 = 0 となるので (n - 1) が因数です。

n³ - 7n + 6 = (n - 1)(n² + n - 6) = (n - 1)(n + 3)(n - 2) = 0

よって n = 1, 2, -3

【Step 4】検証

• n = 1：f(1) = 1 - 7 + 9 = 3 ✓（素数）
• n = 2：f(2) = 8 - 14 + 9 = 3 ✓（素数）
• n = -3：f(-3) = -27 + 21 + 9 = 3 ✓（素数）

【答え】n = -3, 1, 2

【ポイント解説】

この問題は京大整数問題の典型パターンです。

1. mod 3 で考えることで、式が常に3の倍数であることを発見
2. 素数かつ3の倍数 → 3のみ
3. f(n) = 3 の方程式を解く

京都大学の整数問題は約5割以上がmod 3で解けるというデータがあります。京大志望者は必ずマスターしてください！

【問題5】標準：x² + y² = z² + 1 を満たす正の整数の組 (x, y, z) で x ≤ y となるものを全て求めよ

【難易度】★★★☆☆（標準〜発展）

【出題傾向】国公立中堅〜難関大、私立上位大

【解法】

【Step 1】mod 4 で考える

平方数の mod 4 での振る舞いを思い出しましょう。

• 偶数の平方：(2k)² = 4k² ≡ 0 (mod 4)
• 奇数の平方：(2k+1)² = 4k² + 4k + 1 ≡ 1 (mod 4)

つまり、平方数は mod 4 で 0 か 1 のみ。

【Step 2】右辺を分析

z² + 1 について：

• z が偶数のとき：z² ≡ 0 (mod 4) → z² + 1 ≡ 1 (mod 4)
• z が奇数のとき：z² ≡ 1 (mod 4) → z² + 1 ≡ 2 (mod 4)

【Step 3】左辺を分析

x² + y² の mod 4 での値を調べます。

【Step 4】条件を組み合わせる

x² + y² = z² + 1 が成り立つには、両辺の mod 4 が一致する必要があります。

• z が偶数のとき：右辺 ≡ 1 (mod 4) → 左辺も 1 (mod 4) → x, y の一方が偶数、一方が奇数
• z が奇数のとき：右辺 ≡ 2 (mod 4) → 左辺も 2 (mod 4) → x, y が共に奇数

【Step 5】具体的な解を探す

式を変形すると：x² + y² - z² = 1

小さい値から探索します。x ≤ y に注意。

x = 1 のとき：

1 + y² - z² = 1 → y² = z² → y = z（正の整数）

任意の正の整数 y について (1, y, y) は解。

検証：1² + y² = 1 + y² = y² + 1 ✓

x ≥ 2 で他の解を探す：

x² + y² = z² + 1 → x² - 1 = z² - y² = (z-y)(z+y)

x = 2 のとき：4 - 1 = 3 = (z-y)(z+y)

z - y = 1, z + y = 3 → z = 2, y = 1 だが x ≤ y より不適

x = 3 のとき：9 - 1 = 8 = (z-y)(z+y)

可能な組み合わせ：(1,8), (2,4)

• z - y = 1, z + y = 8 → z = 4.5（整数でない）
• z - y = 2, z + y = 4 → z = 3, y = 1 だが x ≤ y より不適

このように探索を続けると、x ≥ 2 では x ≤ y を満たす解は見つかりません。

【答え】(x, y, z) = (1, n, n)（n は任意の正の整数）

【ポイント解説】

mod 4 による平方数の性質を使って、解の候補を絞り込むのが鍵です。最終的には地道な探索も必要ですが、mod による分析で探索範囲を大幅に狭められます。

【問題6】難関：7^n + 12n - 1 が 144 で割り切れる正の整数 n を全て求めよ

【難易度】★★★★★（超難関）

【出題傾向】東大・京大・東工大・旧帝大レベル

【解法】

144 = 16 × 9 = 2⁴ × 3² と素因数分解できます。

f(n) = 7^n + 12n - 1 とおき、f(n) ≡ 0 (mod 144) となる n を求めます。

【Step 1】mod 9 で考える

7 ≡ -2 (mod 9) より、

7^n ≡ (-2)^n (mod 9)

また、12n ≡ 3n (mod 9)、-1 ≡ -1 (mod 9)

よって f(n) ≡ (-2)^n + 3n - 1 (mod 9)

(-2)^n の周期を調べます：

• n = 1：-2 ≡ 7 (mod 9)
• n = 2：4 (mod 9)
• n = 3：-8 ≡ 1 (mod 9)
• n = 4：-2 ≡ 7 (mod 9)
• n = 5：4 (mod 9)
• n = 6：1 (mod 9)

周期は 6 です（オイラーの定理：φ(9) = 6）。

n ≡ 1 (mod 6) のとき：f(n) ≡ 7 + 3n - 1 ≡ 6 + 3n ≡ 3(2 + n) (mod 9)

f(n) ≡ 0 (mod 9) となるには n ≡ 7 ≡ 1 (mod 3) かつ n ≡ 1 (mod 6)

n = 1 のとき：f(1) = 7 + 12 - 1 = 18 ≡ 0 (mod 9) ✓

n ≡ 2 (mod 6) のとき：f(n) ≡ 4 + 3n - 1 ≡ 3 + 3n ≡ 3(1 + n) (mod 9)

9 | f(n) となるには 3 | (1 + n)、つまり n ≡ 2 (mod 3)

n ≡ 2 (mod 6) かつ n ≡ 2 (mod 3) → n ≡ 2 (mod 6) のとき常に成立

n ≡ 3 (mod 6) のとき：f(n) ≡ 1 + 3n - 1 ≡ 3n ≡ 0 (mod 9)

9 | 3n となるには 3 | n、つまり n ≡ 0 (mod 3)。n ≡ 3 (mod 6) は n ≡ 0 (mod 3) なので成立。

同様に他のケースも分析すると、n が偶数のときに mod 9 の条件を満たしやすいことがわかります。

【Step 2】mod 16 で考える

7² = 49 ≡ 1 (mod 16) より、7^n の周期は 2。

• n が奇数のとき：7^n ≡ 7 (mod 16)
• n が偶数のとき：7^n ≡ 1 (mod 16)

12n (mod 16)：12n の値は n によって変化

f(n) ≡ 0 (mod 16) の条件を調べます。

n が偶数のとき：f(n) ≡ 1 + 12n - 1 ≡ 12n (mod 16)

12n ≡ 0 (mod 16) となるには n ≡ 0 (mod 4)（12 × 4 = 48 ≡ 0 mod 16）

さらに詳しく分析すると、n = 12k（12の倍数）のときに両方の条件を満たすことがわかります。

【Step 3】検証

n = 12 のとき：

7^12 + 12 × 12 - 1 = 7^12 + 143

7^12 = (7^2)^6 = 49^6

49 ≡ 1 (mod 48) より、7^12 ≡ 1 (mod 48)

よって 7^12 + 143 ≡ 1 + 143 ≡ 144 ≡ 0 (mod 144) ✓

【答え】n = 12k（k は正の整数）、すなわち n は 12 の正の倍数

【ポイント解説】

この問題は中国剰余定理の応用です。144 を素因数分解し、mod 9 と mod 16 それぞれで条件を調べ、最後に組み合わせます。フェルマーの小定理やオイラーの定理を活用して累乗の周期性を把握することが鍵です。

【問題7】応用：a³ + b³ = c³ を満たす正の整数は存在しないことを、mod 9 を用いて説明せよ（フェルマーの最終定理 n=3 の部分）

【難易度】★★★★☆（発展・教養）

【出題傾向】論述問題・記述式の探究問題として出題される可能性あり

【解法（概要）】

注意：完全な証明は高校範囲を超えますが、mod 9 の活用を示す好例です。

【Step 1】立方数の mod 9 での振る舞い

任意の整数 n について、n (mod 9) は 0, 1, 2, ..., 8 のいずれかです。

n³ (mod 9) を計算します：

重要な発見：立方数は mod 9 で -1, 0, 1 のみ取る！

【Step 2】a³ + b³ = c³ を mod 9 で分析

a³, b³, c³ がそれぞれ -1, 0, 1 のいずれかを取るとき、a³ + b³ ≡ c³ (mod 9) となる組み合わせを調べます。

可能な値の組み合わせ（a³ + b³ の値）：

• -1 + (-1) = -2
• -1 + 0 = -1
• -1 + 1 = 0
• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 1 = 2

c³ ≡ -1, 0, 1 (mod 9) なので、a³ + b³ ≡ -2 や 2 となるケースは矛盾。

つまり、a, b が共に ≡ ±1 (mod 3) の場合は、mod 9 で矛盾が生じます。

残るケースでは a, b, c のいずれかが 3 の倍数となりますが、そこからさらに「無限降下法」という手法で矛盾を導きます（高校範囲外）。

【ポイント解説】

この問題は、mod を使って「ありえない組み合わせ」を排除する典型例です。整数問題では、全ての場合を直接調べるのではなく、mod で候補を絞り込むことが極めて重要です。

ステップ別 実践ガイド

ここまで学んだ内容を、実際の学習に落とし込むためのステップを示します。

【Phase 1】基礎固め（1〜2週間）

目標：mod の基本概念と6つの性質を完璧に理解する

やるべきこと：

1. 合同式の定義を10回書いて覚える
2. 6つの性質を自分の言葉で説明できるようにする
3. 以下の計算を全て暗算でできるようにする：
   • 0〜10 の各数を mod 2, 3, 4, 5 で表す
   • 平方数（1, 4, 9, 16, 25, ...）を mod 3, 4 で表す
4. 教科書の例題を全て解く

チェックポイント：

• 「17 ≡ ? (mod 5)」が即答できる
• 「n² を mod 4 で考えると？」に答えられる
• 「合同式で割り算ができない理由」を説明できる

【Phase 2】パターン習得（2〜3週間）

目標：頻出パターンを身につけ、「法の選び方」を体得する

やるべきこと：

1. 余りを求める問題を20問解く（3^100 ÷ 7 の余り など）
2. 倍数証明問題を15問解く（n³ - n が6の倍数 など）
3. 不定方程式を10問解く（ユークリッド互除法との併用）
4. 各問題で「なぜこの mod を選んだか」を言語化する

重要な暗記事項：

【Phase 3】実戦演習（3〜4週間）

目標：入試問題を時間内に解けるようにする

やるべきこと：

1. 過去問演習：志望校の整数問題を5年分以上解く
2. 時間を計る：1問15〜25分を目安に
3. 復習ノート作成：間違えた問題の「mod 選びのポイント」を記録
4. 類題演習：間違えたパターンの類題を3問ずつ解く

志望校別の傾向：

【Phase 4】総仕上げ（1〜2週間）

目標：どんな整数問題にも対応できる状態へ

やるべきこと：

1. 未見問題への対応訓練：模試や他大学の問題を解く
2. 解法の言語化：「なぜ mod 3 を選んだか」を30秒で説明する練習
3. 弱点の最終補強：苦手パターンを集中演習
4. 本番想定練習：時間プレッシャーの中で解く

よくある質問と回答

Q1. mod を使わなくても解ける問題で、わざわざ mod を使う必要はありますか？

A1. 使えるなら絶対に使うべきです。

mod を使う最大のメリットは「計算ミスの削減」