平方剰余

同義語：2次剰余quadratic residue

概要

前提知識: 合同式, 素数, 互いに素, 剰余類
平方剰余は、「整数 $a$ がある法 $n$ のもとで平方数に合同になるか」、すなわち $2$ 次の合同式 $x^2\equiv a\pmod n$ が整数解をもつかどうかを表す概念である。平方数の記事で見たように、平方数を $4$ や $8$ で割った余りは限られた値しかとらず、これが整数の性質を調べる簡単な道具になる。法を $2$ でない素数 $p$ にすると、$p$ と互いに素な余りのうちちょうど半分が平方数の余りになり、どれがそうかは $a^{(p-1)/2}$ の余りで判定できる（Euler の規準）。平方剰余の判定を法 $p$ と法 $q$ の間で結びつけるのが平方剰余の相互法則であり、初等整数論の中心的な定理の 1 つである。本記事は平方剰余の定義・基本例・基本性質を扱い、相互法則は言明にとどめる。
以下、整数 $a,b$ と正の整数 $n$ について $a\equiv b\pmod n$ は $n\mid a-b$ を表す。

定義

平方剰余と平方非剰余

$n\ge2$ を整数、$a$ を $\gcd(a,n)=1$ を満たす整数とする。

合同式 $x^2\equiv a\pmod n$ が整数解 $x$ をもつとき、$a$ を $n$ を法とする 平方剰余（quadratic residue）という。
解をもたないとき、$a$ を $n$ を法とする 平方非剰余（quadratic nonresidue）という。
$a$ が平方剰余かどうかは $a$ の法 $n$ の剰余類だけで決まるので、法 $n$ の剰余類についても平方剰余・平方非剰余という。

この定義では $n$ と互いに素な $a$ だけを分類し、$\gcd(a,n)>1$ の $a$（たとえば $a\equiv0$）はどちらにも含めない。文献によっては $x^2\equiv a$ が解をもつ $a$ をすべて平方剰余と呼び、$0$ を含めるものもあるので、読むときには流儀を確かめる必要がある。
法が奇素数 $p$ のとき、平方剰余かどうかを数値で表す記号を使う。

平方剰余を表す記号

$p$ を奇素数、$a$ を整数とする。
$$ \left(\frac{a}{p}\right):=\begin{cases}1&(p\nmid a\text{ で、}a\text{ は }p\text{ を法とする平方剰余}),\\-1&(p\nmid a\text{ で、}a\text{ は }p\text{ を法とする平方非剰余}),\\0&(p\mid a)\end{cases} $$
とおき、これを Legendre 記号 という（Legendre記号）。

$p$ は素数なので、$p\nmid a$ と $\gcd(a,p)=1$ は同じ条件である。

直感

$x$ を $0$ から $n-1$ まで動かして $x^2$ の余りを並べると、同じ値が何度も現れ、現れない値もある。平方剰余とは、$n$ と互いに素な値のうち「現れる値」のことである。奇素数 $p$ を法とすると、$x$ と $-x$ は同じ平方を与え、それ以外に重なりはないので、$1,\dots,p-1$ の半分がちょうど 2 回ずつ現れ、残りの半分は一度も現れない。この「半分ずつ」という対称性が、平方剰余どうしの積が平方剰余、平方非剰余どうしの積も平方剰余という乗法の規則（符号 $\pm1$ の掛け算と同じ規則）を生む。

例と反例

小さな素数を法とする平方剰余

$1\le x\le(p-1)/2$ の $x^2$ の余りを計算すると、次の表を得る（prop-quadratic-residue-count により、これで平方剰余がすべて尽くされる）。

$p$	平方剰余	平方非剰余
$3$	$1$	$2$
$5$	$1,4$	$2,3$
$7$	$1,2,4$	$3,5,6$
$11$	$1,3,4,5,9$	$2,6,7,8,10$
$13$	$1,3,4,9,10,12$	$2,5,6,7,8,11$

たとえば $p=13$ では $1^2,2^2,\dots,6^2$ の余りが $1,4,9,3,12,10$ である。$p=7$ では $3^2=9\equiv2$ なので $2$ は平方剰余であり、$x^2\equiv2\pmod7$ の解は $x\equiv3,4$ である。

反例：法 8 と法 15 では半分にならない

法が合成数のときは、$n$ と互いに素な余りのうち平方剰余は半分とは限らない。

法 $8$：奇数 $x=2k+1$ について $x^2=4k(k+1)+1$ であり、$k(k+1)$ は偶数なので $x^2\equiv1\pmod8$ である。よって $8$ と互いに素な余り $1,3,5,7$ のうち平方剰余は $1$ だけで、4 個中 1 個である。
法 $15$：$15$ と互いに素な余り $1,2,4,7,8,11,13,14$ の平方の余りは順に $1,4,1,4,4,1,4,1$ であり、平方剰余は $1,4$ の 2 個だけで、8 個中 2 個である。
いずれも「法と互いに素な余りのちょうど半分が平方剰余である」という奇素数の場合の性質（prop-quadratic-residue-count）を破る。破れているのは法が奇素数であるという仮定である。

反例：合成数の法では平方非剰余どうしの積が平方非剰余になりうる

法 $15$ では ex-quadratic-residue-composite-count により平方剰余は $1,4$ だけなので、$2$ と $7$ はどちらも平方非剰余である。その積 $14$ も平方剰余 $1,4$ のどちらとも合同でないので平方非剰余である。これは、奇素数を法とするとき成り立つ「平方非剰余どうしの積は平方剰余」（prop-quadratic-residue-multiplicative）が、合成数の法では破れることを示す。
さらに、$2$ は法 $3$ でも法 $5$ でも平方非剰余である（上の表）。$15$ を法とする Jacobi記号は Legendre 記号の積 $\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)=(-1)(-1)=1$ で定義されるので値は $1$ だが、$2$ は法 $15$ の平方剰余でない。したがって「Jacobi 記号の値が $1$ なら平方剰余」という含意は成り立たない。

性質

以下この節では、$p$ を奇素数とし、$G:=(\mathbb{Z}/p\mathbb{Z})^\times$ を法 $p$ の単元群（$p$ と互いに素な剰余類が乗法についてなす群、位数 $p-1$）とする。$a$ が法 $p$ の平方剰余であることは、$a$ の剰余類が $G$ のある元の平方であることと同じである。

平方剰余の個数

平方剰余はちょうど半分

平方写像 $s\colon G\to G$、$s(x)=x^2$ は群準同型であり、その核は $\{\pm1\}$、像 $Q:=s(G)$ は $p$ を法とする平方剰余の剰余類全体である。$Q$ は位数 $(p-1)/2$ の部分群であり、
$$ Q=\Bigl\{1^2,\ 2^2,\ \dots,\ \Bigl(\frac{p-1}{2}\Bigr)^2\Bigr\}\pmod p $$
で、右辺の $(p-1)/2$ 個は法 $p$ で相異なる。特に $1,\dots,p-1$ のうち平方剰余と平方非剰余はちょうど $(p-1)/2$ 個ずつある。

$G$ は可換群なので $(xy)^2=x^2y^2$ であり、$s$ は群準同型である。像が平方剰余の類全体であることは定義そのものである。
核を求める。$x^2\equiv1\pmod p$ は $p\mid(x-1)(x+1)$ と同値であり、$p$ は素数なので Euclidの補題により $x\equiv1$ または $x\equiv-1$ と同値である。$p$ は奇数なので $1\not\equiv-1\pmod p$ であり、核 $\{\pm1\}$ はちょうど 2 元からなる。
準同型定理により $G/\{\pm1\}\cong Q$ なので、$|Q|=|G|/2=(p-1)/2$ である。$x$ と $-x$ は同じ平方を与え、$1,\dots,p-1$ の各元は $1\le x\le(p-1)/2$ の $x$ か $-x$ のどちらかに合同なので、$Q$ は $1^2,\dots,((p-1)/2)^2$ の類からなる。これらの個数は高々 $(p-1)/2$ で、$|Q|=(p-1)/2$ なので相異なる。$\square$

同じ個数は、$x^2\equiv y^2$ を直接調べる初等的な方法でも得られる（平方数の記事の命題「奇素数を法とする平方数の剰余の個数」）。上の証明は、それを群の言葉で言い換えたものである。

乗法の規則

平方剰余と平方非剰余の積

$p$ と互いに素な整数 $a,b$ について、次が成り立つ。

$a,b$ がともに平方剰余なら、$ab$ は平方剰余である。
一方が平方剰余で他方が平方非剰余なら、$ab$ は平方非剰余である。
$a,b$ がともに平方非剰余なら、$ab$ は平方剰余である。
すなわち、すべての整数 $a,b$ について $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ である。

prop-quadratic-residue-count により $Q$ は $G$ の指数 $2$ の部分群である。$G$ は可換なので $Q$ は正規部分群であり、剰余群 $G/Q$ は位数 $2$ の群、すなわち $\{Q,\ cQ\}$（$c\notin Q$）である。位数 $2$ の群では単位元でない元の平方は単位元なので、$\chi\colon G\to\{\pm1\}$ を $Q$ の元で $1$、$Q$ に属さない元で $-1$ と定めると、$\chi$ は $G\to G/Q\cong\{\pm1\}$ の合成であり群準同型である。よって $\chi(ab)=\chi(a)\chi(b)$ となり、1〜3 はこの等式の値ごとの言い換えである。$p\mid a$ または $p\mid b$ のときは $p\mid ab$ なので、Legendre 記号の等式は両辺が $0$ で成り立つ。$\square$

3 は群 $G/Q$ の位数が $2$ であることに依存しており、ex-quadratic-residue-composite-product が示すように合成数の法では成り立たないことがある。

Eulerの規準

法 p での根の個数

$f(x)=c_dx^d+\cdots+c_0$ を整数係数の多項式で、$d\ge0$、$p\nmid c_d$ とする。このとき $f(r)\equiv0\pmod p$ を満たす法 $p$ の剰余類 $r$ は高々 $d$ 個である。

$d$ についての帰納法で示す。$d=0$ なら $f=c_0$ で $p\nmid c_0$ なので根はない。$d\ge1$ とし、根 $r$ が 1 つあるとする（なければ示すことはない）。$f(x)$ を $x-r$ で割ると、整数係数の多項式 $g$ で $f(x)=(x-r)g(x)+f(r)$ となるものがあり（除法の原理。$x-r$ はモニックなので商は整数係数）、$g$ は次数 $d-1$ で最高次係数は $c_d$ である。$s$ を $r$ と合同でない根とすると、$0\equiv f(s)\equiv(s-r)g(s)\pmod p$ であり、$p\nmid s-r$ なので Euclid の補題により $g(s)\equiv0$ である。帰納法の仮定により $g$ の根は高々 $d-1$ 個なので、$f$ の根は $r$ を合わせて高々 $d$ 個である。$\square$

Eulerの規準

$p$ を奇素数、$a$ を $p\nmid a$ を満たす整数とする。$a$ が平方剰余なら $a^{(p-1)/2}\equiv1\pmod p$、平方非剰余なら $a^{(p-1)/2}\equiv-1\pmod p$ である。すなわち、すべての整数 $a$ について
$$ a^{(p-1)/2}\equiv\left(\frac{a}{p}\right)\pmod p $$
である。

$a\equiv x^2$ が平方剰余なら、$p\nmid x$ なので Fermatの小定理により $a^{(p-1)/2}\equiv x^{p-1}\equiv1\pmod p$ である。したがって prop-quadratic-residue-count の $(p-1)/2$ 個の平方剰余の類はすべて $f(x)=x^{(p-1)/2}-1$ の根である。lem-quadratic-residue-lagrange により $f$ の根は高々 $(p-1)/2$ 個なので、$f$ の根はちょうど平方剰余の類であり、平方非剰余 $a$ では $a^{(p-1)/2}\not\equiv1$ である。
一方、$p\nmid a$ ならいつも $\bigl(a^{(p-1)/2}\bigr)^2=a^{p-1}\equiv1\pmod p$ なので、prf-quadratic-residue-count の核の計算と同じく $a^{(p-1)/2}\equiv\pm1$ である。平方非剰余では $1$ でないので $-1$ である。$p\mid a$ のときは両辺が $0$ と合同である。$\square$

Eulerの規準の計算

$p=13$ とする。$(p-1)/2=6$ であり、$3^6=729=13\cdot56+1\equiv1$ なので $3$ は平方剰余（実際 $4^2=16\equiv3$）、$2^6=64=13\cdot4+12\equiv-1$ なので $2$ は平方非剰余である。これは ex-quadratic-residue-small-primes の表と一致する。大きな $p$ でも、$a^{(p-1)/2}\bmod p$ は反復 2 乗により $p$ の桁数の多項式時間で計算できるので、平方剰余の判定は平方根を探さずにできる。

−1 が平方剰余となる素数

奇素数 $p$ について、$-1$ が $p$ を法とする平方剰余であることと $p\equiv1\pmod4$ であることは同値である。すなわち $\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}$ である。

thm-quadratic-residue-euler により $\left(\frac{-1}{p}\right)\equiv(-1)^{(p-1)/2}\pmod p$ である。両辺は $\pm1$ で、$p\ge3$ なので $1\not\equiv-1\pmod p$ であり、合同から等式が従う。$(-1)^{(p-1)/2}=1$ は $(p-1)/2$ が偶数、すなわち $p\equiv1\pmod4$ と同値である。$\square$

たとえば $p=13$ では $5^2=25\equiv-1$、$p=5$ では $2^2\equiv-1$ であり、$p=7$ では ex-quadratic-residue-small-primes の表で $6\equiv-1$ が平方非剰余である。

4 で割って 1 余る素数の無限性

$p\equiv1\pmod4$ を満たす素数は無限に存在する。

そのような素数が有限個 $p_1,\dots,p_k$ しかないとし（$k=0$ でもよい）、$N:=(2p_1\cdots p_k)^2+1$ とおく。$N\ge5$ は奇数なので奇素数 $q$ で割り切れる。$y:=2p_1\cdots p_k$ とおくと $y^2\equiv-1\pmod q$ で、$q\nmid y$ である（$q\mid y$ なら $q\mid N-y^2=1$ となる）。よって $-1$ は $q$ を法とする平方剰余であり、cor-quadratic-residue-minus-one により $q\equiv1\pmod4$ である。一方 $q$ は $y$ を割らないので $p_1,\dots,p_k$ のどれとも異なる。これは仮定に反する。$\square$

2 の場合と相互法則

$-1$ の次に基本的なのは、$2$ が奇素数 $p$ を法とする平方剰余かどうか、および奇素数 $q$ が $p$ を法とする平方剰余かどうかであり、次の定理がそれを決める。

第2補充法則と相互法則

$p,q$ を相異なる奇素数とする。

$\left(\dfrac{2}{p}\right)=(-1)^{(p^2-1)/8}$ である。すなわち、$2$ が $p$ を法とする平方剰余であることと $p\equiv\pm1\pmod8$ であることは同値である。
（平方剰余の相互法則）$\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}$ である。すなわち、$p,q$ の少なくとも一方が $4$ で割って $1$ 余るなら $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$、両方が $4$ で割って $3$ 余るなら $\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)$ である。

相互法則の出典

1 と 2 は Gauss の補題（$a^{(p-1)/2}$ の符号を $a,2a,\dots,\frac{p-1}2a$ の余りのうち $p/2$ を超えるものの個数で数える）などを使って証明される。証明は IR90 Chapter 5 と HW08 Chapter VI に譲る。相互法則は Euler と Legendre によって定式化され、Gauss が最初の完全な証明を与えた（IR90 Chapter 5 の注）。相互法則そのものは平方剰余の相互法則の記事で扱う。

cor-quadratic-residue-minus-one と 1 を合わせて第 1・第 2 補充法則と呼ぶことがある。prop-quadratic-residue-multiplicative により $\left(\frac{a}{p}\right)$ は $a$ の素因数分解に沿って積に分かれるので、これらの法則を組み合わせると、任意の $a$ の平方剰余性を小さな数の場合に帰着させて判定できる。

相互法則による判定

$5$ は $11$ を法とする平方剰余か。$5\equiv1\pmod4$ なので $\left(\frac{5}{11}\right)=\left(\frac{11}{5}\right)=\left(\frac{1}{5}\right)=1$ であり、平方剰余である。実際 $4^2=16\equiv5\pmod{11}$ である。
$3$ は $7$ を法とする平方剰余か。$3\equiv7\equiv3\pmod4$ なので $\left(\frac{3}{7}\right)=-\left(\frac{7}{3}\right)=-\left(\frac{1}{3}\right)=-1$ であり、平方非剰余である。これは ex-quadratic-residue-small-primes の表と一致する。
$2$ は $7\equiv-1\pmod8$ を法として平方剰余（$3^2\equiv2$）、$13\equiv5\pmod8$ を法として平方非剰余である（ex-quadratic-residue-euler）。
$6$ は $23$ を法とする平方剰余か。$23\equiv-1\pmod8$ なので $\left(\frac{2}{23}\right)=1$、$3\equiv23\equiv3\pmod4$ なので $\left(\frac{3}{23}\right)=-\left(\frac{23}{3}\right)=-\left(\frac{2}{3}\right)=1$ であり、$\left(\frac{6}{23}\right)=1$ である。実際 $11^2=121=23\cdot5+6$ である。

合成数を法とする平方剰余

合成数の法は、中国剰余定理により素数冪の法に分解される。

素数冪への分解

$n=p_1^{e_1}\cdots p_k^{e_k}$（$p_i$ は相異なる素数、$e_i\ge1$）とし、$\gcd(a,n)=1$ とする。$a$ が $n$ を法とする平方剰余であることと、各 $i$ について $a$ が $p_i^{e_i}$ を法とする平方剰余であることは同値である。

$x^2\equiv a\pmod n$ なら、各 $p_i^{e_i}$ は $n$ を割るので $x^2\equiv a\pmod{p_i^{e_i}}$ である。逆に、各 $i$ について $x_i^2\equiv a\pmod{p_i^{e_i}}$ となる $x_i$ があるとする。$p_1^{e_1},\dots,p_k^{e_k}$ は対ごとに互いに素なので、中国剰余定理により $x\equiv x_i\pmod{p_i^{e_i}}$（すべての $i$）を満たす整数 $x$ がある。このとき各 $i$ で $p_i^{e_i}\mid x^2-a$ であり、対ごとに互いに素な数がすべて割る数はその積でも割り切れるので、$n\mid x^2-a$ である。$\square$

素数冪を法とする平方剰余

$e\ge1$ とする。

$p$ が奇素数で $p\nmid a$ なら、$a$ が $p^e$ を法とする平方剰余であることと、$p$ を法とする平方剰余であることは同値である。
$a$ が奇数なら、$a$ は $2$ を法とする平方剰余である。$a$ が $4$ を法とする平方剰余であることは $a\equiv1\pmod4$ と同値であり、$e\ge3$ のとき $a$ が $2^e$ を法とする平方剰余であることは $a\equiv1\pmod8$ と同値である。

素数冪の場合の証明の所在

1 の「$p^e$ で平方剰余なら $p$ で平方剰余」は明らかである。逆は、$f(x)=x^2-a$ の法 $p$ の根 $x_1$ について $f'(x_1)=2x_1\not\equiv0\pmod p$（$p$ は奇数で $p\nmid x_1$）なので、合成数を法とする合同式の記事の定理「単根のHensel持ち上げ」を $e-1$ 回使えば法 $p^e$ の根が得られる。2 の $e\ge3$ の場合の証明は IR90 Chapter 5 に譲る。「平方剰余なら $a\equiv1\pmod8$」の向きは ex-quadratic-residue-composite-count の 1 と同じ計算で分かる（法 $2^e$ で $x^2\equiv a$ なら法 $8$ でも成り立つ）。$e=2$ の場合は、奇数の平方がいつも $1$ と合同であることから従う。

prop-quadratic-residue-crt と thm-quadratic-residue-prime-power により、$\gcd(a,n)=1$ のとき $a$ が $n$ を法とする平方剰余かどうかは、$n$ の各奇素因数 $p$ について $\left(\frac{a}{p}\right)=1$ かどうかと、$n$ を割る $2$ の冪に応じた $a\bmod 8$ の条件とで決まる。たとえば法 $15$ の平方剰余は $\left(\frac{a}{3}\right)=\left(\frac{a}{5}\right)=1$ となる $a$、すなわち $a\equiv1\pmod3$ かつ $a\equiv\pm1\pmod5$ を満たす $a\equiv1,4\pmod{15}$ であり、ex-quadratic-residue-composite-count の計算と一致する。

補足

原始根と平方剰余

奇素数 $p$ を法とする原始根 $g$（$G$ の生成元。存在は IR90 Chapter 4）をとると、$G$ の元は $g^k$（$0\le k< p-1$）と一意に書ける。このとき $g^k$ が平方剰余であることと $k$ が偶数であることは同値である。実際 $k$ が偶数なら $g^k=(g^{k/2})^2$ であり、逆に $g^k=(g^j)^2$ なら $g^{k-2j}=1$ から $p-1\mid k-2j$ で、$p-1$ は偶数なので $k$ も偶数である。この見方では、Legendre 記号は $G\cong\mathbb{Z}/(p-1)\mathbb{Z}$ から $\mathbb{Z}/2\mathbb{Z}\cong\{\pm1\}$ への唯一の全射準同型であり、prop-quadratic-residue-multiplicative と thm-quadratic-residue-euler がともに見通しよく理解できる。有限体 $\mathbb{F}_q$（$q$ は奇数）でも、乗法群が巡回群であることから、平方元が $\mathbb{F}_q^\times$ のちょうど半分をなすことが同じように分かる。