平方剰余
$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$
合同式:定理2.2より、$3n+2$ の形の平方数は存在しない。同じようにして、$4n+3, 5n+2, 5n+3, \ldots$ のような形の平方数も存在しないことがわかる。
一方、$3n+1, 4n+1, 5n+1, 5n+4, \ldots$ のような形の平方数は存在する。
与えられた整数 $a, k$ に対して $kn+a (n\in\ZZ)$ の形の平方数が存在することは合同式 $$x^2\equiv a\mathmod{k}$$ が解をもつことと同値である。このとき、$a$ を $k$ を法とする平方剰余といい（あるいは$a\mathmod{k}$ を平方剰余といい）、 そうでないとき $a$ を $k$ を法とする平方非剰余という（あるいは$a\mathmod{k}$ を平方非剰余という）。
とくに、法 $p$ が素数である場合、Legendre記号 $(a/p)$ を、
- $\gcd(a, p)=1$ で $a$ が $p$ を法とする平方剰余ならば $(a/p)=1$
- $\gcd(a, p)=1$ で $a$ が $p$ を法とする平方非剰余ならば $(a/p)=-1$
- $p\mid a$ ならば $(a/p)=0$
と定義する。 この項目では、Legendre記号のとる値について解説する。すなわち素数を法とする平方剰余について解説する。
基本的性質
定理1.1
奇素数 $p$ を法とする原始根 $g$ をひとつとる。 $p$ と互に素な整数 $a$ について、$g$ を底とする $a$ の指数を $k$ とおくと $$\left(\frac{a}{p}\right)=1\Longleftrightarrow 2\mid k$$ が成り立つ。
Proof.
$(a/p)=1$ のとき $$x^2\equiv g^k\equiv a\mathmod{p}$$ となる $x$ が存在する。 $$g^{k(p-1)/2}\equiv x^{k(p-1)}\equiv 1\mathmod{p}$$ であるが、$g$ は原始根なので $k/2$ は整数、すなわち $k$ は偶数となる。
逆に $k=2m$ が偶数のとき $$(g^m)^2\equiv g^k\equiv a\mathmod{p}$$ となるから $(a/p)=1$ である。
□定理1.2
$p$ が奇素数のとき $$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\mathmod{p}.$$
Proof.
$p$ と互に素な整数 $a$ について、$g$ を底とする $a$ の指数を $k$ とおく。 $(a/p)=1$ のとき 定理1.1より $k$ は偶数であるから $$a^{(p-1)/2}\equiv g^{k(p-1)/2}\equiv 1\mathmod{p}$$ となる。また $(a/p)=-1$ のとき $k$ は奇数であるから $$a^{(p-1)/2}\equiv g^{k(p-1)/2}\equiv g^{(p-1)/2}\equiv -1\mathmod{p}$$ となる。$(a/p)=0$ のときは $$\left(\frac{a}{p}\right)\equiv 0\equiv a^{(p-1)/2}\mathmod{p}$$ となる。
□このことからすぐに、次の事実が導かれる。
定理1.3
$$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right).$$
Proof.
$p\mid (ab)$ ならば両辺ともに $0$ となるので、$\gcd(a, p)=\gcd(b, p)=1$ としてよい。さらにこのとき $p=2$ ならば両辺ともに $1$ となるので、$p$ は奇数としてよい。 このとき定理1.2 より $$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\equiv a^{(p-1)/2}b^{(p-1)/2}\equiv (ab)^{(p-1)/2}\equiv \left(\frac{ab}{p}\right)\mathmod{p}$$ がすぐにわかるが、$p>2$ なので $$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)$$ となる。
□また、定理1.2の特別な場合として、$(-1/p)$ が決定される。
第1補充法則
$p$ が奇素数のとき $$\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}=\left\{\begin{array}{cl}1 & (p\equiv 1\mathmod{4})\\ -1 & (p\equiv 3\mathmod{4}).\end{array}\right.$$
なお、$p\equiv 3\mathmod{4}$ のときに $(-1/p)=-1$ となることは合同式: 定理4.2からすぐにわかる。 第1補充法則からは、逆に、$p\equiv 1\mathmod{4}$ ならばかならず $p\mid (n^2+1)$ となる整数 $n$ が存在することがわかる。
Gaussの補題と第2補充法則
Gaussの補題
$p$ を奇素数とし、$a$ を $p$ で割り切れない整数とする。 $ak (k=1, 2, \ldots, (p-1)/2)$ を $p$ で割った余りを $r_k$ とし、 $r_k>p/2$ となる $k$ の個数を $\mu$ とおくと $$\left(\frac{a}{p}\right)=(-1)^\mu.$$
Proof.
$$s_k=\left\{\begin{array}{cl}r_k & (r_k\leq (p-1)/2)\\ p-r_k & (r_k\geq (p-1)/2)\end{array}\right.$$ とおく。 $k=1, 2, \ldots, (p-1)/2$ に対して $p$ は $ak$ を割り切らないから $r_k\neq 0$ なので $s_k\neq 0$ となる。 よって $1\leq s_k\leq (p-1)/2$ がつねに成り立つ。
一方、$s_k=s_\ell$ ならば $k=\ell$ となる。実際このとき $r_k=r_\ell$ または $r_k=p-r_\ell$ となるが、$2\leq k+\ell\leq p-1$ より $$r_k+r_\ell\equiv a(k+\ell)\not\equiv 0\mathmod{p}$$ となるので、$r_k=r_\ell$ つまり $$r_k-r_\ell\equiv a(k-\ell)\equiv 0\mathmod{p}$$ となり、$\abs{k-\ell}<p$ より $k=\ell$ でなければならない。
よって、$s_k (k=1, 2, \ldots, (p-1)/2)$ は $1, 2, \ldots, (p-1)/2$ を$1$回ずつとるので $$\prod_{k=1}^{(p-1)/2} s_k\equiv \left[\frac{p-1}{2}\right]!\mathmod{p}$$ となる。また $$\prod_{k=1}^{(p-1)/2} r_k\equiv \prod_{k=1}^{(p-1)/2} (ak)\equiv a^{(p-1)/2} \left[\frac{p-1}{2}\right]!\equiv \left(\frac{a}{p}\right)\left[\frac{p-1}{2}\right]!\mathmod{p}$$ となる。一方 $$s_k\equiv \left\{\begin{array}{cl}r_k & (r_k\leq (p-1)/2)\\ -r_k & (r_k\geq (p-1)/2)\end{array}\right. \mathmod{p}$$ となるから $$\prod_{k=1}^{(p-1)/2} s_k\equiv (-1)^\mu \prod_{k=1}^{(p-1)/2} r_k \mathmod{p}$$ が成り立つ。よって $$1\equiv (-1)^\mu \left(\frac{a}{p}\right)\mathmod{p}$$ つまり $$\left(\frac{a}{p}\right)\equiv (-1)^{-\mu}\equiv (-1)^\mu \mathmod{p}$$ が成り立つ。
□Gaussの補題からは $(\pm 2/p)$ を決定することができる。
第2補充法則
$p$ が奇素数のとき $$\left(\frac{2}{p}\right)=(-1)^{\frac{p-1}{2}-\floor{\frac{p}{4}}} =\left\{\begin{array}{cl}1 & (p\equiv \pm 1\mathmod{8})\\ -1 & (p\equiv \pm 3\mathmod{8}).\end{array}\right.$$ および $$\left(\frac{-2}{p}\right)=\left\{\begin{array}{cl}1 & (p\equiv 1, 3\mathmod{8})\\ -1 & (p\equiv 5, 7\mathmod{8}).\end{array}\right.$$ が成り立つ。
Proof.
Gaussの補題より $$2, 4, \ldots, p-1$$ のうち、$p/2$ より大きいものの個数を $\mu$ とおくと $$\left(\frac{2}{p}\right)=(-1)^\mu$$ となる。
$$\mu=\frac{p-1}{2}-\floor{\frac{p}{4}}$$ であるから、 $$\left(\frac{2}{p}\right)=(-1)^{\frac{p-1}{2}-\floor{\frac{p}{4}}}$$ となる。 $p\equiv 1\mathmod{4}$ のとき $$\frac{p-1}{2}-\floor{\frac{p}{4}}=\frac{p-1}{2}-\frac{p-1}{4}=\frac{p-1}{4}$$ となる。$p\equiv 1\mathmod{8}$ のとき、右辺は偶数だから $(2/p)=1$ となる, $p\equiv 5\mathmod{8}$ のとき、右辺は奇数だから $(2/p)=-1$ となる。 $p\equiv 3\mathmod{4}$ のとき $$\frac{p-1}{2}-\floor{\frac{p}{4}}=\frac{p-1}{2}-\frac{p-3}{4}=\frac{p+1}{4}$$ となる。$p\equiv 7\mathmod{8}$ のとき、右辺は偶数だから $(2/p)=1$, $p\equiv 3\mathmod{8}$ のとき、右辺は奇数だから $(2/p)=-1$ となる。 これによって $(2/p)$ は決定される。
定理1.3より $$\left(\frac{-2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)$$ となるから、第1補充法則とあわせて $p\equiv 1, 3$ のとき $(-2/p)=1$, $p\equiv 5, 7$ のとき $(-2/p)=-1$ となる。
□
平方剰余の相互法則
$p, q$ がともに奇素数のとき $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{(p-1)(q-1)/4}$$ が成り立つ。
補題3.1
$p, q$ がともに奇素数のとき $$S(q, p)=\sum_{s=1}^{(p-1)/2} \floor{\frac{sq}{p}}$$ とおくと $$S(q, p)+S(p, q)=\frac{(p-1)(q-1)}{4}$$ が成り立つ。
Proof.
$$V=\{(x, y)\in\ZZ^2|1\leq x\leq (p-1)/2, 1\leq y\leq (q/p)x\},$$ $$W=\{(x, y)\in\ZZ^2|1\leq y\leq (q-1)/2, 1\leq x\leq (p/q)y\}$$ とおくと $$\frac{sq}{p}=\#\{y\in\ZZ| 1\leq y\leq sq/p\}=\#\{(s, y)\in\ZZ^2|1\leq y\leq sq/p\}$$ より $$S(q, p)=\# V$$ が成り立つ。同様に $$S(p, q)=\# W$$ となる。 $$U=\ZZ^2\cap ([1, (p-1)/2]\times [1, (q-1)/2])=\{(x, y)\in\ZZ^2|1\leq x\leq (p-1)/2, 1\leq y\leq (q-1)/2\}$$ とおくと $V, W$ は $U$ の部分集合で $$U=V\cup W, V\cap W=\emptyset$$ が成り立つ。実際、$U$ 上の点は $1\leq y\leq (q/p)x$ のとき $V$ に属し $(q/p)x\leq y\leq (q-1)/2$ のとき $x\leq (p/q)y$ となるから $W$ に属する。 また $1\leq x\leq (p-1)/2$ のとき $p$ は $qx$ を割り切らないから $V$ 上の点では $y=(q/p)x$ は成り立たないので $V, W$ は共通部分をもたない。よって $$S(q, p)+S(p, q)=\#V +\#W =\#U = \frac{(p-1)(q-1)}{4}$$ が成り立つ。
□補題3.2
$p, q$ がともに奇素数のとき $$\left(\frac{q}{p}\right)=(-1)^{S(q, p)}.$$
Proof.
$kq (k=1, 2, \ldots, (p-1)/2)$ を $p$ で割った余りを $r_k$ とし $r_k>p/2$ となる $k$ の個数を $\mu$ とおく。また $$s_k=\left\{\begin{array}{cl}r_k & (r_k\leq (p-1)/2)\\ p-r_k & (r_k\geq (p-1)/2)\end{array}\right.$$ とおく。Gaussの補題の証明と同様にして、$s_k$ は $1, 2, \ldots, (p-1)/2$ を1回ずつとるから $$\sum_{k=1}^{(p-1)/2} s_k=\sum_{k=1}^{(p-1)/2} k=\frac{1}{2}\times\frac{p-1}{2}\times\frac{p+1}{2}=\frac{p^2-1}{8}$$ となる。 一方 $$\sum_{k=1}^{(p-1)/2} s_k=\sum_{s_k=r_k} s_k+\sum_{s_k=p-r_k} s_k =\sum_{s_k=r_k} r_k+\sum_{s_k=p-r_k} (p-r_k)=\sum_{s_k=r_k} r_k+ \mu p-\sum_{s_k=p-r_k} r_k$$ だから $$\sum_{s_k=r_k} r_k+ \mu p-\sum_{s_k=p-r_k} r_k=\frac{p^2-1}{8} \quad\quad (3.1)$$ が成り立つ。
定義から $$kq=p\floor{\frac{kq}{p}}+r_k$$ であるから $$q\frac{p^2-1}{8}=pS(q, p)+\sum_{k=1}^{(p-1)/2} r_k$$ となるので $(3.1)$ より $$\frac{(q-1)(p^2-1)}{8}=pS(q, p)-\mu p+2\sum_{s_k=p-r_k} r_k$$ が成り立つ。$p, q$ はともに奇数なので $8\mid (p^2-1)$ より、左辺は偶数であるから $$S(q, p)\equiv \mu\mathmod{2}$$ つまり $$(-1)^\mu=(-1)^{S(q, p)}$$ が成り立つ。よってGaussの補題より $$\left(\frac{q}{p}\right)=(-1)^\mu=(-1)^{S(q, p)}$$ が成り立つ。
□平方剰余の相互法則の証明
補題3.2より $$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{S(q, p)+S(p, q)}$$ となるから補題3.1より $$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{(p-1)(q-1)/4}$$ となる。
系
$p, q$ のいずれかが $4n+1$ の形の素数ならば $8\mid (p-1)(q-1)$ より $$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=1$$ となり $$\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)$$ が成り立つ。 $p, q$ がともに $4n+3$ の形の素数ならば $p-1, q-1$ はともに $2$ で$1$回ずつしか割り切れないので $(p-1)(q-1)/4$ は奇数だから $$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=-1$$ となり $$\left(\frac{q}{p}\right)=-\left(\frac{p}{q}\right)$$ が成り立つ。
与えられた数 $a, p$ に対して平方剰余を求めたいときは、 $a$ を $p$ で割った余り $r$ をとり、$r=\prod q_i^{e_i}$ と素因数分解すると $q_i\leq r<p$ かつ $$\left(\frac{a}{p}\right)=\prod_i \left(\frac{q_i}{p}\right)^{e_i}$$ となるが、平方剰余の相互法則より $$\left(\frac{q_i}{p}\right)=\left(\frac{p}{q_i}\right)(-1)^{(p-1)(q_i-1)/4}$$ となるので、結局より小さな素数 $q_i$ を法とする平方剰余に帰着する。これによって 任意の素数を法とする平方剰余が求められる。
参考文献
第2補充法則および相互法則の証明は G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th Ed. revised by D. R. Heath-Brown and J. H. Silverman, Oxford University Press, 2008, Chapter 6, Section 6.11-6.13, p.p. 92--98 を参考にした。
