整数論まとめ：定義・定理・アルゴリズムを一覧で整理【学部整数論・競技プログラミング】

整数論の全体像を一記事で．整除・合同式からp進数・代数的整数まで，学部整数論と競技プログラミングに必要な定義・定理・アルゴリズムを体系的にまとめた．各トピックの依存関係図付き．

2026年2月27日

1. はじめに：この記事の使い方

この記事は，学部レベルの整数論を一記事で俯瞰することを目的とする．各トピックについて，定義・主要定理・アルゴリズムを簡潔にまとめる．

使い方：

初学者 → セクション順に読み進め，整数論の全体像を掴むとよい
復習・試験対策 → 目次から必要なセクションへジャンプされたい
競プロの確認 → セクション14「定理・アルゴリズム一覧」で主要結果を一覧できる

以下の依存関係図は，各トピックがどのように繋がっているかを示す．

graph TD
    A["整数の整除と合同式"] --> B["GCDとユークリッド互除法"]
    A --> C["素数と算術の基本定理"]
    A --> D["合同式の応用と群構造"]
    B --> D
    C --> D
    D --> E["原始根と離散対数"]
    B --> F["中国剰余定理"]
    D --> F
    D --> G["二次剰余"]
    E --> G
    C --> H["数論的関数"]
    B --> I["連分数"]
    C --> J["素数の分布"]
    C --> K["p進付値"]
    C --> L["代数的整数"]

    style A fill:#f5f5f5,stroke:#333,color:#000
    style D fill:#f5f5f5,stroke:#333,color:#000
    style F fill:#f5f5f5,stroke:#333,color:#000
    style L fill:#f5f5f5,stroke:#333,color:#000

注意 1.

本記事は「整数論の教科書」シリーズの各記事と連携している．各セクション末尾のリンクから，体系的な解説・証明に進むことができる．

2. 整数の整除と合同式

定義 2 (整除).

整数

a, b

（

b \neq = 0

）に対して，

a = b q

となる整数

q

が存在するとき，

b

は

a

を整除する（

b ∣ a

）という．

定理 3 (除法の定理).

任意の整数

a

と正の整数

b

に対して，

a = b q + r

（

0 \leq r < b

）を満たす整数

q, r

が一意に存在する．

定義 4 (合同式).

整数

a, b

と正の整数

m

に対して，

m ∣ (a - b)

のとき

a \equiv b (mod m)

と書き，

a

と

b

は法

m

で合同であるという．

定理 5 (合同式の基本性質).

合同式は同値関係であり，加法・乗法と両立する：

$a \equiv b (mod m)$ かつ $c \equiv d (mod m)$ ならば $a + c \equiv b + d (mod m)$
$a \equiv b (mod m)$ かつ $c \equiv d (mod m)$ ならば $a c \equiv b d (mod m)$

→ 詳しくは：

https://interconnectd.app/articles/4wl50lHKf3yaBjvhB8cz

3. 最大公約数とユークリッド互除法

定義 6 (最大公約数).

整数

a, b

の最大公約数（greatest common divisor）

g cd (a, b)

とは，

a

と

b

の共通の約数のうち最大のものである．

g cd (a, b) = 1

のとき

a, b

は互いに素であるという．

定理 7 (ユークリッド互除法).

a \geq b > 0

のとき，

g cd (a, b) = g cd (b, a mod b)

．

a mod b = 0

のとき

g cd (a, b) = b

．

定理 8 (ベズーの等式).

整数

a, b

に対して

g cd (a, b) = a x + b y

を満たす整数

x, y

が存在する．この

x, y

は拡張ユークリッド互除法で求められる．

主要アルゴリズム：

ユークリッド互除法： $g cd (a, b)$ を計算． $O (lo g (min (a, b)))$
拡張ユークリッド互除法： $g cd (a, b) = a x + b y$ の $x, y$ も同時に計算． $O (lo g (min (a, b)))$

→ 詳しくは：

https://interconnectd.app/articles/rs0vpxGm9F1WMuEdIVep

4. 素数と算術の基本定理

定義 9 (素数).

2

以上の整数

p

で，

1

と

p

以外に正の約数を持たないものを素数（prime）という．素数でない

2

以上の整数を合成数という．

定理 10 (算術の基本定理).

任意の

2

以上の整数

n

は，素数の積として一意に表される（順序を除く）：

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}

定理 11 (素数の無限性).

素数は無限に存在する（Euclid）．

主要アルゴリズム：

試し割り法： $n$ の素因数分解． $O (n)$
エラトステネスの篩： $n$ 以下の全素数を列挙． $O (n lo g lo g n)$
Miller-Rabin素数判定法：確率的素数判定． $O (k lo g^{2} n)$ （ $k$ 回の試行）

→ 詳しくは：

https://interconnectd.app/articles/pxU4vxLqmnzS0rlSelaY

5. 合同式の応用と剰余類の群構造

定義 12 (剰余類).

法

m

による合同関係で

Z

を類別したとき，各同値類を剰余類という．剰余類全体の集合を

Z / m Z

と書く．

定義 13 (既約剰余類群).

(Z / m Z)^{\times} = {a \in Z / m Z ∣ g cd (a, m) = 1}

は乗法に関して群をなす．この群を既約剰余類群という．

定義 14 (オイラーのトーシェント関数).

φ (m) = ∣ (Z / m Z)^{\times} ∣

，すなわち

1

から

m

までの整数のうち

m

と互いに素なものの個数をオイラーのトーシェント関数という．

定理 15 (オイラーの定理).

g cd (a, m) = 1

ならば

a^{φ (m)} \equiv 1 (mod m)

．

定理 16 (フェルマーの小定理).

p

が素数で

p ∤ a

ならば

a^{p - 1} \equiv 1 (mod p)

．

定理 17 (ウィルソンの定理).

p

が素数

⟺

(p - 1)! \equiv - 1 (mod p)

．

主要アルゴリズム：

繰り返し二乗法： $a^{n} mod m$ を計算． $O (lo g n)$
逆元の計算： $g cd (a, m) = 1$ のとき，拡張ユークリッド互除法またはフェルマーの小定理 $a^{p - 2} mod p$ で計算

→ 詳しくは：

https://interconnectd.app/articles/8EDswa8mNLlOJL9943vQ

6. 原始根と離散対数

定義 18 (位数).

g cd (a, m) = 1

のとき，

a^{k} \equiv 1 (mod m)

を満たす最小の正整数

k

を

a

の法

m

における位数（order）といい，

ord_{m} (a)

と書く．

定義 19 (原始根).

ord_{m} (a) = φ (m)

のとき，

a

を法

m

の原始根（primitive root）という．

定理 20 (原始根の存在).

法

m

の原始根が存在する

⟺

m = 1, 2, 4, p^{k}, 2 p^{k}

（

p

は奇素数，

k \geq 1

）のいずれかである．

定義 21 (離散対数).

g

が法

m

の原始根のとき，

g^{x} \equiv a (mod m)

を満たす

x

を

a

の離散対数（discrete logarithm）

ind_{g} a

という．

定理 22 (原始根の個数).

法

m

の原始根が存在するとき，原始根の個数は

φ (φ (m))

個である．

主要アルゴリズム：

Baby-step Giant-step：離散対数問題 $g^{x} \equiv a (mod p)$ を解く． $O (p)$ 時間・空間

→ 詳しくは：

https://interconnectd.app/articles/QT1r0wp8eh4G0tn5iYt0

7. 中国剰余定理と応用

定理 23 (中国剰余定理（CRT）).

m_{1}, m_{2}, \dots, m_{k}

が互いに素（

g cd (m_{i}, m_{j}) = 1

，

i \neq = j

）のとき，連立合同式

x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{k} (mod m_{k})

は法

M = m_{1} m_{2} \dots m_{k}

で一意な解を持つ．

定理 24 (環の同型).

g cd (m_{i}, m_{j}) = 1

（

i \neq = j

）のとき，環の同型

Z / M Z ≅ Z / m_{1} Z \times Z / m_{2} Z \times \dots \times Z / m_{k} Z

が成り立つ．

主要アルゴリズム：

CRTの構成的解法： $M_{i} = M / m_{i}$ として $x \equiv \sum_{i = 1}^{k} a_{i} M_{i} (M_{i}^{- 1} mod m_{i}) (mod M)$ ． $O (k lo g M)$
Garnerのアルゴリズム：CRTを逐次的に適用し，大きな $M$ でのオーバーフローを回避． $O (k^{2})$

→ 詳しくは：

https://interconnectd.app/articles/MzBDh6lTw2UgbpRhXnwJ

8. 二次剰余と相互法則

定義 25 (二次剰余).

p

を奇素数とする．

g cd (a, p) = 1

のとき，

x^{2} \equiv a (mod p)

が解を持つならば

a

は

p

の二次剰余（quadratic residue），持たないならば二次非剰余という．

定義 26 (ルジャンドル記号).

(\frac{a}{p}) = ⎩ ⎨ ⎧ 1 - 1 0 a が p の二次剰余 a が p の二次非剰余 p ∣ a

定理 27 (オイラーの基準).

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p)

定理 28 (二次相互法則（Gauss）).

p, q

を異なる奇素数とするとき

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}

定理 29 (第一補充法則・第二補充法則).

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2}, (\frac{2}{p}) = (- 1)^{(p^{2} - 1) /8}

主要アルゴリズム：

Tonelli-Shanksのアルゴリズム： $x^{2} \equiv a (mod p)$ の解を求める． $O (lo g^{2} p)$

→ 詳しくは：

https://interconnectd.app/articles/5onlEYEhoT5nyddKXjzT

9. 数論的関数と乗法的関数

定義 30 (数論的関数).

正の整数を変数とする複素数値関数

f : Z_{> 0} \to C

を数論的関数（arithmetic function）という．

定義 31 (乗法的関数).

f (1) = 1

であって，

g cd (m, n) = 1

ならば

f (mn) = f (m) f (n)

が成り立つとき，

f

を乗法的（multiplicative）という．任意の

m, n

で

f (mn) = f (m) f (n)

が成り立つとき完全乗法的という．

定義 32 (主要な数論的関数).

オイラー関数 $φ (n)$ ： $n$ と互いに素な $1 \leq k \leq n$ の個数
約数関数 $σ_{k} (n) = \sum_{d ∣ n} d^{k}$ ．特に $σ_{0} (n) = d (n)$ （約数の個数）， $σ_{1} (n) = σ (n)$ （約数の和）
メビウス関数 $μ (n)$ ： $n = 1$ のとき $1$ ， $n$ が相異なる素数の積のとき $(- 1)^{k}$ （ $k$ は素因数の個数），それ以外は $0$

定理 33 (メビウスの反転公式).

F (n) = \sum_{d ∣ n} f (d)

ならば

f (n) = \sum_{d ∣ n} μ (n / d) F (d)

．

定義 34 (ディリクレ畳み込み).

(f * g) (n) = \sum_{d ∣ n} f (d) g (n / d)

をディリクレ畳み込み（Dirichlet convolution）という．乗法的関数のディリクレ畳み込みは再び乗法的である．

主要アルゴリズム：

$φ (n)$ の計算： $n$ の素因数分解から $φ (n) = n \prod_{p ∣ n} (1 - 1/ p)$ ． $O (n)$
篩を用いた一括計算： $n$ 以下のすべての $φ (k)$ , $μ (k)$ を $O (n lo g lo g n)$ で計算

→ 詳しくは：

https://interconnectd.app/articles/beTVUjLudO4MFFhXEdtN

10. 連分数とディオファントス近似

定義 35 (連分数展開).

実数

α

の（正則）連分数展開とは

α = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{⋱}}} = [a_{0}; a_{1}, a_{2}, \dots]

の形の表示をいう．

a_{0} \in Z

，

a_{i} \in Z_{> 0}

（

i \geq 1

）である．

α

が有理数

⟺

連分数展開が有限で終わる．

定義 36 (近似分数).

[a_{0}; a_{1}, \dots, a_{n}]

を

α

の第

n

近似分数（convergent）

p_{n} / q_{n}

という．漸化式

p_{n} = a_{n} p_{n - 1} + p_{n - 2}, q_{n} = a_{n} q_{n - 1} + q_{n - 2}

で計算される．

定理 37 (最良近似性).

α

の近似分数

p_{n} / q_{n}

は，分母が

q_{n}

以下の有理数のうち

α

に最も近いもの（最良有理近似）である．

定理 38 (Lagrangeの定理).

α

が二次無理数

⟺

α

の連分数展開が（ある項以降）周期的である．

定理 39 (ペル方程式).

D

が平方数でない正の整数のとき，

x^{2} - D y^{2} = 1

の正の整数解は

D

の連分数展開の近似分数から得られる．

→ 詳しくは：

https://interconnectd.app/articles/yz8tV2R0GkILVmuIijTg

11. 素数の分布

定義 40 (素数計数関数).

π (x) = # {p \leq x ∣ p は素数}

を素数計数関数という．

定理 41 (素数定理).

π (x) \sim \frac{x}{ln x} (x \to \infty)

すなわち

lim_{x \to \infty} \frac{π ( x )}{x / l n x} = 1

が成り立つ．

定義 42 (チェビシェフ関数).

θ (x) = \sum_{p \leq x} ln p

，

ψ (x) = \sum_{p^{k} \leq x} ln p

をチェビシェフ関数という．

定理 43 (チェビシェフの定理).

十分大きな

x

に対して定数

c_{1}, c_{2} > 0

が存在して

c_{1} \frac{x}{ln x} \leq π (x) \leq c_{2} \frac{x}{ln x}

定理 44 (算術級数の素数定理（Dirichlet）).

g cd (a, m) = 1

ならば，

a, a + m, a + 2 m, \dots

の中に素数は無限に存在する．

注意 45.

リーマン予想は，

ζ (s) = \sum_{n = 1}^{\infty} n^{- s}

の非自明な零点がすべて

Re (s) = 1/2

上にあるという未解決問題であり，

π (x)

の精密な評価と密接に関係する．

→ 詳しくは：

https://interconnectd.app/articles/2w0V0JCD7UJQrMbyRM6D

12. p進付値と局所的手法

定義 46 (p進付値).

素数

p

と

0

でない整数

n

に対して，

n

を割り切る

p

の最大べき指数を

v_{p} (n)

と書き，

p

進付値（

p

-adic valuation）という．

v_{p} (0) = + \infty

と定める．

定義 47 (p進絶対値).

∣ n ∣_{p} = p^{- v_{p} (n)}

（

n \neq = 0

），

∣0 ∣_{p} = 0

を

p

進絶対値という．

定理 48 (p進付値の性質).

$v_{p} (ab) = v_{p} (a) + v_{p} (b)$
$v_{p} (a + b) \geq min (v_{p} (a), v_{p} (b))$ （超距離不等式に対応）
等号条件： $v_{p} (a) \neq = v_{p} (b)$ のとき $v_{p} (a + b) = min (v_{p} (a), v_{p} (b))$

定義 49 (p進整数環と

p

進数体).

p

進絶対値に関する

Q

の完備化を

p

進数体

Q_{p}

という．

Z_{p} = {x \in Q_{p} ∣ ∣ x ∣_{p} \leq 1}

を

p

進整数環という．

定理 50 (Henselの補題).

f (x) \in Z_{p} [x]

に対して，

f (a) \equiv 0 (mod p)

かつ

f^{'} (a) \neq \equiv 0 (mod p)

ならば，

f (α) = 0

かつ

α \equiv a (mod p)

なる

α \in Z_{p}

が存在する．

定理 51 (Legendre記号との関係).

p

が奇素数で

g cd (a, p) = 1

のとき，

x^{2} \equiv a (mod p)

が解を持つ

⟺

x^{2} = a

が

Q_{p}

で解を持つ（Henselの補題による持ち上げ）．

→ 詳しくは：

https://interconnectd.app/articles/blTCmBbhP9Mfz9yGgKZD

13. 代数的整数入門

定義 52 (代数的整数).

α \in C

がモニック（最高次係数が

1

）な整数係数多項式の根であるとき，

α

を代数的整数（algebraic integer）という．代数的整数全体の集合は環をなす．

定義 53 (数体と整数環).

Q

の有限次拡大

K

を代数体（number field）という．

K

の元のうち代数的整数であるものの全体を

O_{K}

と書き，

K

の整数環という．

例 54 (二次体).

K = Q (d)

（

d

は平方因子を持たない整数）のとき

O_{K} = {Z [d] Z [\frac{1 + d}{2}] d \equiv 2, 3 (mod 4) d \equiv 1 (mod 4)

定義 55 (イデアル).

O_{K}

のイデアル

a

とは，加法について部分群であり

O_{K} \cdot a \subseteq a

を満たすものをいう．

定理 56 (イデアルの一意分解).

O_{K}

の

0

でないイデアルは，素イデアルの積として一意に分解される（順序を除く）：

a = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{r}^{e_{r}}

これはデデキント環の基本性質である．

定義 57 (類数).

イデアル類群

Cl (O_{K})

（分数イデアルの同値類がなす群）の位数を類数（class number）

h_{K}

という．

h_{K} = 1

⟺

O_{K}

が一意分解整域（UFD）である．

定理 58 (Minkowskiの限界).

類数を計算するにあたり，すべてのイデアル類はノルムがMinkowskiの限界

M_{K}

以下の素イデアルの積で代表される：

M_{K} = \frac{n !}{n ^{n}} (\frac{4}{π})^{r_{2}} ∣ Δ_{K} ∣

ここで

n = [K : Q]

，

r_{2}

は複素埋め込みの対の数，

Δ_{K}

は判別式である．

→ 詳しくは：

https://interconnectd.app/articles/XxSYQHuhZr9FAejqkn4r

14. 定理・アルゴリズム一覧

学部整数論と競技プログラミングで登場する主要な定理とアルゴリズムの一行サマリーである．

基本定理：

除法の定理： $a = b q + r$ （ $0 \leq r < b$ ）が一意に存在
算術の基本定理：正整数は素数の積として一意に分解
ベズーの等式： $g cd (a, b) = a x + b y$ なる整数 $x, y$ が存在
フェルマーの小定理： $p ∤ a \Rightarrow a^{p - 1} \equiv 1 (mod p)$
オイラーの定理： $g cd (a, m) = 1 \Rightarrow a^{φ (m)} \equiv 1 (mod m)$
ウィルソンの定理： $p$ が素数 $⟺ (p - 1)! \equiv - 1 (mod p)$
中国剰余定理：互いに素な法に関する連立合同式は一意に解ける
原始根の存在： $m = 1, 2, 4, p^{k}, 2 p^{k}$ のときのみ存在
二次相互法則： $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}$
メビウスの反転公式： $F = f * 1 \Rightarrow f = F * μ$
素数定理： $π (x) \sim x / ln x$
Dirichletの算術級数定理： $g cd (a, m) = 1$ なら $a + km$ に素数は無限

代数的構造の定理：

CRTの環同型： $Z / M Z ≅ \prod Z / m_{i} Z$
Henselの補題： $mod p$ の単根は $Z_{p}$ の根に持ち上がる
イデアルの一意分解：デデキント環で素イデアル分解は一意
Lagrangeの定理（連分数）：二次無理数 $⟺$ 周期的連分数

主要アルゴリズム：

ユークリッド互除法（GCD）： $O (lo g (min (a, b)))$
拡張ユークリッド互除法（GCD + ベズー係数）： $O (lo g (min (a, b)))$
エラトステネスの篩（素数列挙）： $O (n lo g lo g n)$
試し割り法（素因数分解）： $O (n)$
Miller-Rabin（素数判定）： $O (k lo g^{2} n)$
繰り返し二乗法（べき乗剰余）： $O (lo g n)$
CRT構成的解法： $O (k lo g M)$
Garnerのアルゴリズム（CRT）： $O (k^{2})$
Baby-step Giant-step（離散対数）： $O (p)$
Tonelli-Shanks（平方根 $mod p$ ）： $O (lo g^{2} p)$
$φ (n)$ の計算（素因数分解経由）： $O (n)$

整数論代数学まとめ定理一覧アルゴリズム競技プログラミング

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

整数論まとめ：定義・定理・アルゴリズムを一覧で整理【学部整数論・競技プログラミング】

1. はじめに：この記事の使い方

2. 整数の整除と合同式

3. 最大公約数とユークリッド互除法

4. 素数と算術の基本定理

5. 合同式の応用と剰余類の群構造

6. 原始根と離散対数

7. 中国剰余定理と応用

8. 二次剰余と相互法則

9. 数論的関数と乗法的関数

10. 連分数とディオファントス近似

11. 素数の分布

12. p進付値と局所的手法

13. 代数的整数入門

14. 定理・アルゴリズム一覧

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ