二次剰余と相互法則 ― 平方剰余の理論

ルジャンドル記号を定義し，オイラーの規準を証明する．ガウスの補題を経て二次の相互法則を証明し，ヤコビ記号への拡張とTonelli-Shanksアルゴリズムを解説する．

2026年2月27日

1 二次剰余

定義 1 (二次剰余).

奇素数

p

と

p ∤ a

なる整数

a

に対して，

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

が解を持つとき

a

は

p

の二次剰余（quadratic residue）であるといい，解を持たないとき二次非剰余（quadratic non-residue）であるという．

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

奇素数

p

と整数

a

に対してルジャンドル記号を

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

と定める．

定理 3.

1, 2, \dots, p - 1

のうち

p

の二次剰余は

(p - 1) /2

個，二次非剰余も

(p - 1) /2

個である．

証明.

写像

f : (Z / p Z)^{*} \to (Z / p Z)^{*}

を

f (\overset{x}{ˉ}) = \overset{x}{ˉ}^{2}

で定める．

f (\overset{x}{ˉ}) = f (\overset{y}{ˉ})

⟺

\overset{x}{ˉ}^{2} = \overset{y}{ˉ}^{2}

⟺

\overset{x}{ˉ} = \pm \overset{y}{ˉ}

．よって各二次剰余はちょうど2つの元の像であり，二次剰余の個数は

(p - 1) /2

． □

2 オイラーの規準

定理 4 (オイラーの規準).

奇素数

p

と

p ∤ a

なる整数

a

に対して

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

証明.

a

が二次剰余のとき

a \equiv x^{2}

なので

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

（フェルマーの小定理）．多項式

t^{(p - 1) /2} - 1

は

(Z / p Z)^{*}

上で高々

(p - 1) /2

個の根を持ち，二次剰余

(p - 1) /2

個がすべて根である．よって

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

⟺

a

は二次剰余．

a^{p - 1} \equiv 1

より

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

なので

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

．二次非剰余のとき

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

． □

3 ガウスの補題

補題 5 (ガウスの補題).

奇素数

p

と

p ∤ a

に対して，

a, 2 a, 3 a, \dots, \frac{p - 1}{2} a

の

mod p

での値を

{- (p - 1) /2, \dots, - 1, 1, \dots, (p - 1) /2}

の範囲で代表元を取ったとき，負の代表元の個数を

μ

とすると

(\frac{a}{p}) = (- 1)^{μ} .

証明.

s_{1}, s_{2}, \dots, s_{(p - 1) /2}

を上の代表元とする．

∣ s_{1} ∣, ∣ s_{2} ∣, \dots, ∣ s_{(p - 1) /2} ∣

は

{1, 2, \dots, (p - 1) /2}

の並べ替えである（

∣ s_{i} ∣ = ∣ s_{j} ∣

なら

ia \equiv \pm ja (mod p)

で

i = j

または

i + j \equiv 0

だが

1 \leq i, j \leq (p - 1) /2

より後者は不可）．よって

\prod s_{i} = (- 1)^{μ} \cdot ((p - 1) /2)!

かつ

\prod s_{i} \equiv \prod_{i = 1}^{(p - 1) /2} ia = ((p - 1) /2)! \cdot a^{(p - 1) /2}

．両辺を

((p - 1) /2)!

で割って

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

．オイラーの規準から結論を得る． □

4 平方剰余の第一補充法則

定理 6 (平方剰余の第一補充法則).

奇素数

p

に対して

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2} = {1 - 1 p \equiv 1 (mod 4), p \equiv 3 (mod 4) .

すなわち

- 1

が

p

の二次剰余であることと

p \equiv 1 (mod 4)

は同値である．

証明.

オイラーの規準より

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

である．

(- 1)^{(p - 1) /2} = \pm 1

であり，

p \geq 3

なので

mod p

で

1 \neq \equiv - 1

である．よって

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

が整数としての等式で成り立つ．

p \equiv 1 (mod 4)

のとき

(p - 1) /2

は偶数なので

(\frac{- 1}{p}) = 1

（

- 1

は二次剰余）．

p \equiv 3 (mod 4)

のとき

(p - 1) /2

は奇数なので

(\frac{- 1}{p}) = - 1

（

- 1

は二次非剰余）． □

5 二次の相互法則

定理 7 (二次の相互法則).

相異なる奇素数

p, q

に対して

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

証明.

ガウスの補題を用いて

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

の

μ

を格子点の計数に帰着する．矩形

R = {(x, y) ∣ 1 \leq x \leq (p - 1) /2, 1 \leq y \leq (q - 1) /2}

を考える．

q x mod p

の負の代表元の個数

μ

は，直線

y = q x / p

の下方にある格子点のうち

y > (q - 1) /2 - q x / p

に相当する部分の計数と一致する．対称的な議論により

μ + μ^{'} = (p - 1) (q - 1) /4

が導かれ（

μ^{'}

は

(\frac{p}{q}) = (- 1)^{μ^{'}}

の指数），

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{(p - 1) (q - 1) /4}

が得られる． □

6 ヤコビ記号

定義 8 (ヤコビ記号).

奇数

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

（

p_{i}

は奇素数，重複可）に対して

(\frac{a}{n}) = \prod_{i = 1}^{k} (\frac{a}{p _{i}})

．

注意 9.

ヤコビ記号は相互法則を保ち，素因数分解を行わずに効率的に計算できる（

O (lo g^{2} n)

）．ただし

(\frac{a}{n}) = 1

でも

a

が

n

の二次剰余とは限らない点に注意が必要である．

7 Tonelli-Shanks アルゴリズム

注意 10.

a

が素数

p

の二次剰余であるとき

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

の解を求めるアルゴリズムが Tonelli-Shanks 法である．

p - 1 = 2^{s} q

（

q

は奇数）と分解し，二次非剰余

z

を用いて反復的に解を構成する．計算量は

O (lo g^{2} p)

である．

二次剰余と相互法則 ― 平方剰余の理論

1 二次剰余

2 オイラーの規準

3 ガウスの補題

4 平方剰余の第一補充法則

5 二次の相互法則

6 ヤコビ記号

7 Tonelli-Shanks アルゴリズム

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

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

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

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

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