文献あり

平方剰余まとめ

617

はじめまして, 今回は自分の初投稿の記事ということで平方剰余の性質について証明とともに解説することにしました. 文章に飛躍や誤りなどありましたらコメント欄にて教えていただけると幸いです.

まずは平方剰余記号, 別名 $Legendre$ 記号の定義から.

平方剰余記号の定義

$p$ を奇素数, $a$ を $gcd (a, p) = 1$ を満たす整数とするとき,
$(\frac{a}{p}) \overset{def}{=} \begin{array}{r} {\begin{cases} + 1 (\exists x \in Z; x^{2} \equiv a (\mod p)) \\ - 1 (\forall x \in Z; x^{2} ≢ a (\mod p)) \end{cases} \end{array}$
$+ 1$ となるとき, $a$ は $x$ の平方剰余, $- 1$ となるとき, $a$ は $x$ の平方非剰余であるという.

平方剰余記号が乗法的であること

$ψ (a) = (\frac{a}{p})$ なる $ψ : F_{p}^{*} \to {\pm 1}$ は群の全射準同型となる. (ただし, $F_{p}^{*}$ は $Z / p Z$ の乗法群)

$ψ$ の全射性は明らか.
$G = F_{p}^{*}$ , $H$ を $G$ の元を $2$ 乗して得られる $G$ の部分群とする.
文献[2]の命題1.11.38より、有限体の乗法群である $G$ は巡回群である.
したがって $G$ の生成元を $g$ とすれば, $G = {g, \dots, g^{\frac{p - 1}{2}}, \dots, g^{p - 1} = 1}$ と表され, $H = {g^{2}, \dots, g^{p - 1} = 1, g^{p + 1} = g^{2}, \dots, g^{2 (p - 1)}} = {g^{2}, \dots, g^{p - 1} = 1}$ となる. よって $x \in G$ が平方剰余か否かは $H$ に属するか否かであるから, $x = g^{n}$ なる $n$ の偶奇によって定まる. したがって $ψ$ が準同型であることは偶奇の和の性質から容易に分かる.

Eulerの基準

$(\frac{a}{p}) = 1 \Leftrightarrow a^{\frac{p - 1}{2}} \equiv 1 (\mod p)$

群準同型 $φ : F_{p}^{*} \to F_{p}^{*}$ を $φ (a) = a^{\frac{p - 1}{2}}$ で定める. また, $ψ$ を命題１と同様に定義する.
定義より $\forall a \in \ker (ψ); \exists n \in F_{p}^{*}; a = n^{2}$ であり, $Fermat$ の小定理より $φ (a) = n^{p - 1} = 1$ の成立から $\ker (ψ) \subset \ker (ϕ)$ が従い, $| \ker (ψ) | \leq | \ker (φ) |$ を得る. また, 命題１における $G$ と $H$ の比較から, $F_{p}^{*} = 2 | \ker (ψ) |$ が分かる. したがって, $Lagrange$ の定理より群の位数はその部分群の位数の整数倍であるから, $| \ker (ψ) | = | \ker (φ) |$ または $| \ker (φ) | = | F_{p}^{*} |$ が成立. (追記:ここで, 準同型の核が部分群となることを用いた. これは形式算によって確かめられる.)
後者の成立を仮定すると多項式 $x^{\frac{p - 1}{2}} - 1 = 0$ は $p - 1$ 個の相異なる解を持つことになるが, 文献[2]の系1.2.13(体の元を係数に持つ多項式は高々その次数個しか解を持たないという有名事実, 帰納的に示される)に反するため不合理.
$∴ | \ker (ψ) | = | \ker (φ) | \Leftrightarrow \ker (ψ) = \ker (ϕ)$ となり, 題意は示された.

平方剰余の相互法則

相異なる奇素数 $p, q$ について次が成立.
$(\frac{p}{q}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} (\frac{q}{p})$

この定理は証明が少し複雑で, 多少の下準備を要します. 以下 $ζ = ζ_{p}$ , すなわち $1$ の $p$ 乗根とします.

Gauss和

整数 $a$ , 奇素数 $p$ に対し,
$g_{a} \overset{def}{=} \sum_{n = 1}^{p - 1} (\frac{n}{p}) ζ^{a n}$

いくつか性質を.

$g_{0} = 0$ (命題１の証明より検証はやさしい.)
$\sum_{n = 0}^{p - 1} ζ^{a n} = \begin{array}{r} {\begin{cases} p, if a \equiv 0 (\mod p) \\ 0, otherwise. \end{cases} \end{array}$
前者は明らか, 後者は $(与式) = \frac{ζ^{a p} - 1}{ζ - 1} = \frac{1 - 1}{ζ - 1} = 0$ より示される.
$\forall a \in Z; g_{a} = g_{1} (\frac{a}{p})$
$a \equiv 0 (\mod p)$ の場合は性質１より従う. $a ≢ 0 (\mod p)$ の場合は平方剰余記号は乗法的で, $a$ での乗法は $F_{p}$ 上での全単射となるため $g_{a} (\frac{a}{p}) = \sum_{n = 0}^{p - 1} ζ^{a n} (\frac{a n}{p}) = \sum_{m = 0}^{p - 1} ζ^{m} (\frac{m}{p}) = g_{1}$
よって,両辺に $(\frac{a}{p})$ をかければ求めていた式を得る.

$p$ で割り切れない全ての $a$ について $g_{a}^{2} = (- 1)^{\frac{p - 1}{2}} p$ が成立.

$g_{a} g_{- a}$ を $2$ 通りの方法で求める.
乗法性, Eulerの基準より $g_{a} g_{- a} = (- 1)^{\frac{p - 1}{2}} g_{1}^{2}$ が確かめられる.
よって $\sum_{a = 0}^{p - 1} g_{a} g_{- a} = (p - 1) (- 1)^{\frac{p - 1}{2}} g_{1}^{2}$ を得る.
また, 定義より
$g_{a} g_{- a} = \sum_{n = 0}^{p - 1} (\frac{n}{p}) ζ^{a n} \cdot \sum_{m = 0}^{p - 1} (\frac{m}{p}) ζ^{- a m} = \sum_{n = 0}^{p - 1} \sum_{m = 0}^{p - 1} (\frac{n}{p}) (\frac{m}{p}) ζ^{a n - a m}$
よって
$\begin{array}{rcl} \sum_{a = 0}^{p - 1} g_{a} g_{- a} & = & \sum_{a = 0}^{p - 1} \sum_{n = 0}^{p - 1} \sum_{m = 0}^{p - 1} (\frac{n}{p}) (\frac{m}{p}) ζ^{a n - a m} \\ = & \sum_{n = 0}^{p - 1} \sum_{m = 0}^{p - 1} (\frac{n}{p}) (\frac{m}{p}) \sum_{a = 0}^{p - 1} ζ^{a n - a m} \end{array}$
ここで性質２より, $n \equiv m (\mod p)$ (ここでは $n = m$ と同等)のときかつそのときに限り $\sum_{a = 0}^{p - 1} ζ^{a n - a m} = p$ , それ以外のときは $0$ となる. したがって式は $\sum_{n = 0}^{p - 1} {(\frac{n}{p})}^{2} p = p (p - 1)$ に帰着される.
また, 性質３より $g_{a}^{2} = {(\frac{a}{p})}^{2} g_{1}^{2} = g_{1}^{2}$ であることと併せると, $g_{a}^{2} = (- 1)^{\frac{p - 1}{2}} p$ が結論付けられる.

それでは本題の相互法則の証明に入ります. 一応主張をもう一度ここに記しておきましょう.

平方剰余の相互法則

相異なる奇素数 $p, q$ について次が成立.
$(\frac{p}{q}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} (\frac{q}{p})$

$Z [ζ] / (q)$ 上で考える.
$p^{*} = (- 1)^{\frac{p - 1}{2}} p, g = g_{1}$ とする.
$(p^{*})^{\frac{q - 1}{2}} = (\frac{p^{*}}{q})$ が $Euler$ の基準より従い, 補題４より $g^{q - 1} = (g^{2})^{\frac{q - 1}{2}} = (p^{*})^{\frac{q - 1}{2}}$ であるから, 両辺を $g$ 倍すると $g^{q} = g (\frac{p^{*}}{q})$ を得る. また,二項定理より得られる $(x + y)^{n} \equiv x^{n} + y^{n} (\mod n)$ より
$g^{q} = {(\sum_{n = 0}^{p - 1} (\frac{n}{p}) ζ^{n})}^{q} = \sum_{n = 0}^{p - 1} {(\frac{n}{p})}^{q} ζ^{n q} = \sum_{n = 0}^{p - 1} (\frac{n}{p}) ζ^{n q} = g_{q}$
性質３より, $g_{q} = g (\frac{q}{p})$
よって $g (\frac{p^{*}}{q}) = g (\frac{q}{p})$ であり, $g \neq q$ であるから $(\frac{p^{*}}{q}) = (\frac{q}{p})$
また,
$LHS = (\frac{(- 1)^{(p - 1 / 2)} p}{q}) = {(\frac{- 1}{q})}^{(p - 1 / 2)} (\frac{p}{q}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} (\frac{p}{q})$
この両辺に $(- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}$ をかけると求めていたものが得られる.