数論初級では何を学びますか？

合同式（モジュラー算術）を中心に、フェルマーの小定理、オイラーの定理、中国剰余定理、原始根などの古典的な整数論の定理を学びます。これらはRSA暗号など現代の暗号理論の基礎となります。

数論初級の前提知識は何ですか？

入門レベルの内容（約数・倍数、素数、ユークリッドの互除法）と、基本的な証明の読み書きが前提です。高校数学を修了していれば十分取り組めます。

合同式とは何ですか？

2つの整数 a, b が正整数 n で割った余りが等しいとき、a ≡ b (mod n) と書き「a と b は n を法として合同」といいます。時計の12時間制（mod 12）が身近な例です。合同式では加法・減法・乗法が自由に行えますが、除法には条件が必要です。

数論初級

Elementary Number Theory

初級（大学1-2年レベル）

English version

この章について

数論初級では、合同式（モジュラー算術）を中心に学ぶ。フェルマーの小定理、オイラーの定理、中国剰余定理など、数論の古典的で重要な定理を習得する。これらは現代の暗号理論（RSA暗号など）の基礎となる。

前提知識

入門レベルの内容（約数・倍数、素数、ユークリッドの互除法）
基本的な証明の読み書き

主要な定理

フェルマーの小定理

$p$ を素数、$a$ を $p$ と互いに素な整数とするとき、

$$a^{p-1} \equiv 1 \pmod{p}$$

オイラーの定理

$n$ を正整数、$a$ を $n$ と互いに素な整数とするとき、

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

ここで $\varphi(n)$ は $1$ 以上 $n$ 以下で $n$ と互いに素な整数の個数。

中国剰余定理

$m_1, m_2, \ldots, m_k$ が互いに素であるとき、連立合同式

$$x \equiv a_i \pmod{m_i} \quad (i = 1, 2, \ldots, k)$$

は $\bmod M = m_1 m_2 \cdots m_k$ で一意な解を持つ。

このレベルで理解できる応用

RSA暗号

現代のインターネットセキュリティの基盤。2つの大きな素数 $p, q$ の積 $n = pq$ を公開し、$\varphi(n) = (p-1)(q-1)$ を秘密にする。オイラーの定理により $m^{ed} \equiv m \pmod{n}$ となる $e, d$ を用いて暗号化・復号を行う。素因数分解の困難性が安全性の根拠。

擬似乱数生成

線形合同法 $x_{n+1} = ax_n + c \pmod{m}$ は最も基本的な擬似乱数生成器。パラメータの選び方（$a, c, m$ の関係）に数論的条件が必要で、原始根の概念も関係する。

ハッシュ関数

データ構造のハッシュテーブルでは、キーを素数 $p$ で割った余りをインデックスにすることが多い。素数を使うと衝突（異なるキーが同じ場所に入る）が減る。これは素数の「割り切れにくさ」による。

素数判定

フェルマーの小定理を使った素数判定（フェルマーテスト）：$a^{n-1} \not\equiv 1 \pmod{n}$ なら $n$ は合成数。ただしカーマイケル数という例外があり、完全ではない。ミラー・ラビン法はこれを改良したもの。

学習のポイント

合同式に慣れる：通常の等式と合同式の違い（特に除法）を理解する
オイラーの $\varphi$ 関数：素因数分解との関係を把握する
群論との関連：$(\mathbb{Z}/n\mathbb{Z})^*$ が乗法群をなすことを意識する
応用を意識：RSA暗号を通じて理論の実用性を体感する

数論初級

この章について

前提知識

目次

1. 合同式の基礎

2. 合同式の演算

3. フェルマーの小定理

4. オイラーの定理

5. 中国剰余定理

6. 原始根

7. 暗号への応用

補遺. 不定方程式

補遺. ハミング数

補遺. タクシー数

補遺. エラトステネスの篩

補遺. コラッツ予想

補遺. 素数の無限性（解析的証明）

補遺. 72の法則

8. 演習問題