二次剰余の世界 ― なぜ「平方数 mod p」は半分しかないのか

x→x^2 が 2:1 写像であることから二次剰余が (p-1)/2 個しかない理由を直感的に理解し，ルジャンドル記号，オイラーの規準，二次の相互法則の「驚き」，Tonelli-Shanks アルゴリズムを解説します．

2026年2月27日

$mod 7$ で $1^{2} = 1, 2^{2} = 4, 3^{2} = 2, 4^{2} = 2, 5^{2} = 4, 6^{2} = 1$ ．平方数は ${1, 2, 4}$ の 3 つだけ ― ${1, 2, 3, 4, 5, 6}$ のちょうど半分です．これは偶然ではありません．この記事では， $mod p$ の世界での平方数の振る舞いと，そこから生まれる深い理論を解説します．

1 二次剰余の定義

定義 1 (二次剰余).

p

を奇素数，

g cd (a, p) = 1

とします．

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

をみたす

x

が存在するとき，

a

を

p

の二次剰余（quadratic residue）と呼びます．存在しないとき二次非剰余（quadratic non-residue）と呼びます．

例 2.

p = 7

のとき，

{1, 2, \dots, 6}

の各元の平方を

mod 7

で計算すると：

1^{2} \equiv 1, 2^{2} \equiv 4, 3^{2} \equiv 2, 4^{2} \equiv 2, 5^{2} \equiv 4, 6^{2} \equiv 1

二次剰余は

{1, 2, 4}

，二次非剰余は

{3, 5, 6}

です．

2 なぜ半分しかないのか ― $x \mapsto x^{2}$ は 2:1 写像

定理 3.

p

を奇素数とするとき，

1, 2, \dots, p - 1

のうち二次剰余は

(p - 1) /2

個，二次非剰余も

(p - 1) /2

個です．

証明.

写像

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

を

f (x) = x^{2}

で定めます．

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

ですから，

x

と

p - x

（

\equiv - x

）は同じ値に写ります．しかも

x \neq = p - x

（

p

が奇素数なので

2 x \neq \equiv 0

）です．

逆に，

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

なら

p ∣ (x - y) (x + y)

．ユークリッドの補題より

x \equiv y

か

x \equiv - y

です．

つまり，各二次剰余はちょうど

2

個の元の像です．像の個数は

(p - 1) /2

． □

注意 4.

直感的に言えば，

{1, 2, \dots, p - 1}

を

{x, - x}

のペアに分けると

(p - 1) /2

個のペアができ，各ペアが1つの二次剰余を生みます．だから二次剰余は

(p - 1) /2

個です．

3 ルジャンドル記号

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

p

を奇素数，

g cd (a, p) = 1

とするとき，

(\frac{a}{p}) = {1 - 1 a が p の二次剰余のとき a が p の二次非剰余のとき

p ∣ a

のときは

(\frac{a}{p}) = 0

と定めます．

注意 6.

ルジャンドル記号は完全乗法的です：

(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p})

．これは「二次剰余

\times

二次剰余 = 二次剰余」「二次剰余

\times

非剰余 = 非剰余」「非剰余

\times

非剰余 = 二次剰余」を意味し，

{1, - 1}

の乗法と一致します．

4 オイラーの規準 ― 効率的な判定法

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

p

を奇素数，

g cd (a, p) = 1

とするとき，

(\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 (mod p)

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

a

が二次非剰余のとき：

x^{p - 1} - 1 \equiv 0 (mod p)

は高々

p - 1

個の根をもちます．

x^{p - 1} - 1 = (x^{(p - 1) /2} - 1) (x^{(p - 1) /2} + 1)

と因数分解できます．二次剰余は

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

の根を

(p - 1) /2

個与えるので，

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

の根はこれで尽きます．残りの

(p - 1) /2

個（二次非剰余）は

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

をみたします． □

注意 8.

オイラーの規準により，

a

が二次剰余かどうかを繰り返し二乗法で

O (lo g p)

で判定できます．素因数分解は不要です．

5 二次の相互法則 ― 整数論で最も驚くべき定理

定理 9 (二次の相互法則（ガウス）).

p, q

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

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

注意 10 (なぜ「驚き」なのか).

(\frac{p}{q})

は「

p

が

mod q

で平方数か」を聞いています．

(\frac{q}{p})

は「

q

が

mod p

で平方数か」を聞いています．この2つの問いはまったく異なる世界（

mod q

と

mod p

）の話なのに，驚くべきことに互いに関係しているのです．

p \equiv q \equiv 3 (mod 4)

のときだけ符号が反転し，それ以外は一致します．ガウスはこの定理を「黄金定理」と呼び，生涯で8通りの証明を与えました．

例 11.

23

は

mod 59

で二次剰余か？直接計算する代わりに相互法則を使います：

(\frac{23}{59}) (\frac{59}{23}) = (- 1)^{11 \times 29} = (- 1)^{319} = - 1

59 \equiv 13 (mod 23)

なので

(\frac{59}{23}) = (\frac{13}{23})

．さらに相互法則を繰り返し適用して簡約できます．

6 Tonelli-Shanks アルゴリズム

二次剰余であることがわかったら，実際に平方根を求めたくなります．

注意 12 (Tonelli-Shanks).

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

の解

x

を求めるアルゴリズムです．

p - 1 = 2^{s} \cdot q

（

q

は奇数）と書き，二次非剰余

n

を1つ見つけて，

a

の平方根を反復的に構成します．計算量は

O (lo g^{2} p)

です．

特殊ケース：

p \equiv 3 (mod 4)

のときは

x \equiv a^{(p + 1) /4} (mod p)

で直接求まります（

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

）．

7 まとめ

$mod p$ の二次剰余はちょうど $(p - 1) /2$ 個です（ $x \mapsto x^{2}$ が 2:1 写像）
ルジャンドル記号は二次剰余性を $\pm 1$ で表す完全乗法的関数です
オイラーの規準により $O (lo g p)$ で判定できます
二次の相互法則は異なる素数間の二次剰余性を結びつける驚くべき定理です
Tonelli-Shanks で $mod p$ の平方根を効率的に計算できます

次の記事では，ユークリッドの互除法の「別の顔」― 連分数と有理近似の世界を探ります．

整数論代数学教科書の行間

Folio公式

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

0 followers·105 articles

二次剰余の世界 ― なぜ「平方数 mod p」は半分しかないのか

1 二次剰余の定義

2 なぜ半分しかないのか ― $x \mapsto x^{2}$ は 2:1 写像

3 ルジャンドル記号

4 オイラーの規準 ― 効率的な判定法

5 二次の相互法則 ― 整数論で最も驚くべき定理

6 Tonelli-Shanks アルゴリズム

7 まとめ

Share your expertise with the world

More from Folio公式

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

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

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

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

1 二次剰余の定義

2 なぜ半分しかないのか ―x↦x2は 2:1 写像

3 ルジャンドル記号

4 オイラーの規準 ― 効率的な判定法

5 二次の相互法則 ― 整数論で最も驚くべき定理

6 Tonelli-Shanks アルゴリズム

7 まとめ

Share your expertise with the world

More from Folio公式

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

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

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

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

2 なぜ半分しかないのか ― $x \mapsto x^{2}$ は 2:1 写像