平方剰余の相互法則についてのメモ - 音楽室と化学室と美術室とPC室の融合部屋　所謂自由室

平方剰余の相互法則についてちょっとちゃんと把握したいなと思ったので，本の式を追って備忘録としてまとめました．

剰余類
ルジャンドル記号
平方剰余の相互法則
参考文献

剰余類

整数 $a,b,m$ に対して $a-b$ が $m$ の倍数なら $a\equiv b\pmod{m}$ と表記する．
例えば $a,b$ それぞれ $m$ で割ったあまりが同じなら $a\equiv b \pmod{m}$ と言っても内容としてはあまり変わらないと思う．

この関係は加減乗は普通の等号と同じように計算ができて， $a\equiv b\pmod{m}$ に対して整数 $c$ を用いて
$a+c\equiv b+c\pmod{m}$
$ac\equiv bc\pmod{m}$
という計算や， $a\equiv b\pmod{m}$ ， $c\equiv d\pmod{m}$ に対して
$a+c\equiv b+d\pmod{m}$
$ac\equiv bd\pmod{m}$
が成り立つ．
商に対しては注意が必要で， $4\equiv 14\pmod{10}$ ではあるが $2\equiv 7\pmod{10}$ とはならない．
商の場合は
$ac\equiv bc \pmod{m}$
の場合，最大公約数 ${\rm GCD}(c,m)$ で $m$ も割ってやらないといけない．
例えば今回の場合 ${\rm GCD}(4,14,10) = 2$ なので $2\equiv 7\pmod{5}$ となる．

基本的に整数では $a,m$ の最大公約数を $d$ とすると
$ax+my = d$ を満たす $x,y$ が存在する．
それは即ち $ax \equiv d \pmod m$ の解が存在するということと同値となる．

オイラーのトーシェント関数

$n\in \mathbb{Z}$ に対し $1\sim n$ の整数 $m$ のうち $n\perp m$ となる $m$ の個数を $\varphi (n)$ と表記する．
特に $p$ が素数なら $\varphi(p) = p-1$ になる．

オイラーの定理とフェルマーの小定理

$a,m\in\mathbb{Z}$ に対し $a\perp m$ なら
$a^{\varphi (m)} \equiv 1 \pmod{m}$
が成り立つ．

これは互いに $m$ と互いに素となる $a_1,a_2, \cdots , a_{\varphi(m)}$ に対して $a$ を乗じた結果はただ順序を入れ替えたものになる．
例えば $a\cdot a_i \equiv a\cdot a_j$ となる場合は $a\perp m$ なので $a_i \equiv a_j \pmod{m}$ となり同じものになる．
こうすると
$a_1a_2\cdots a_{\varphi(m)} \equiv (a\cdot a_1)(a\cdot a_2)\cdots (a\cdot a_{\varphi(m)}) = a^{\varphi(m)}a_1a_2\cdots a_{\varphi(m)} \pmod{m}$
となり， $a_1,a_2,\cdots,a_{\varphi(m)}$ は $m$ と互いに素なので
$1 \equiv a^{\varphi(m)} \pmod{m}$
になる．
これはオイラーの定理と呼ばれ，暗号学では有名なRSA暗号にも応用されている．（現在は楕円曲線暗号が効率が良いので取って代わられかけている．）

特に素数 $p$ の場合は $a^{p-1} \equiv 1 \pmod{p}$ となり，この式はフェルマーの小定理と呼ばれている．

原始根

整数 $m$ と $a\perp m$ となる $a,m$ に対して $a^k\equiv 1 \pmod{m}$ となる最小の $k$ を，位数という．
もちろん $n = kl$ となる $m$ に対しても $a^n \equiv 1 \pmod{m}$ になる．

素数 $p$ のとき，位数が $p-1$ になる数 $a$ が存在し，それを $p$ を法とする原始根という．

原始根は全ての素数に対して存在する．

例えば $p$ を法として $m^a\equiv 1\pmod{p}$ ， $n^b\equiv 1\pmod{p}$ という数を考える場合， $a\perp b$ なら $mn$ は $ab$ が位数になる．
$a\perp b$ でない場合は，最小公倍数 ${\rm lcm}(a,b) = l$ のうち $a$ の約数を $A$ ， $b$ の約数を $B$ とすると $m^{\frac{a}{A}}n^{\frac{b}{B}}$ の位数は $AB$ になり， $AB>a,b$ となるので一段回大きい位数の数が作れる．
これを $1～p-1$ に対して行うと， $p-1$ の約数は $p-1$ 個未満であるので，この操作を繰り返すといつかは $p-1$ が位数となる数が生成できる．

ちなみに原始根 $g$ に対し $n\perp p-1$ となる $n$ を用いて $g^n$ はまた原始根となる．
つまり $p$ の原始根は $\varphi(p-1)$ 個存在する．

ウィルソンの定理

ここで原始根を用いた証明の定番のウィルソンの定理

素数 $p$ に対し $(p-1)! \equiv -1 \pmod {p}$

について．

$p=2$ の場合は自明なので奇素数のみ考える．
$p$ の原始根 $g$ を用いると， $1\sim p-1$ は $g^1,g^2,g^3,\cdots,g^{p-1}$ を並び替えたものなので
$(p-1)! \equiv g^1\cdot g^2 \cdot \cdots \cdot g^{p-1} \pmod{p}$
で，フェルマーの小定理より $g^{p-1} \equiv 1\pmod{p}$ である．
つまり
$(p-1)! \equiv g^{\frac{(p-2)(p-1)}{2}} \pmod{p}$
とまとめることができ，
$(p-1)! \equiv \left(g^{\frac{p-1}{2}}\right)^{p-2} \pmod{p}$
と変形すると，
$\left(g^{\frac{p-1}{2}}\right)^2 = g^{p-1} \equiv 1\pmod{p}$
であるが $g$ は原始根と設定しており，位数は $p-1$ なので
$g^{\frac{p-1}{2}} \equiv -1 \pmod{p}$
つまり
$(p-1)! \equiv \left(-1\right)^{p-2} \pmod{p}$
であるが， $p$ は奇素数なので $p-2$ は奇数．つまり
$(p-1)! \equiv -1 \pmod{p}$
となる．

ルジャンドル記号

整数 $a$ と素数 $p$ に対し
$x^2 \equiv a\pmod{p}$
の解となる $x$ の存在が気になる場合がある．
ここで解が存在する場合， $a$ は $p$ を法として平方剰余，存在しない場合は非平方剰余と言う．

例えば $p = 7,a=2$ の場合， $3^2 \equiv 2 \pmod{7}$ なので2は7を法として平方剰余になる．
ここでルジャンドル記号という記号を定義する．

$\left(\frac{a}{p}\right)$
と分数のように表記し，平方剰余の場合1，非平方剰余の場合-1と値をとることにする．

先程の例でいうと $\left(\frac{2}{7}\right) = 1$ となる．

このルジャンドル記号は原始根 $g$ について考えるととても話が早い．
$n\in\mathbb{Z}$ に対し $a=g^{2n}$ なら $a$ は平方剰余で，そうでないなら非平方剰余になる．シンプル．
簡潔に言うならば， $a=g^i$ ならば $(-1)^i$ となる．
例えば $7$ の原始根は $3,5$ であり，
$3\rightarrow 2\rightarrow 6 \rightarrow 4 \rightarrow 5 \rightarrow 1$
となる．つまり1，2，4は7の平方剰余となる．

$6^2 \equiv 1^2 \equiv 1 \pmod{7}$
$3^2 \equiv 4^2 \equiv 2 \pmod{7}$
$2^2 \equiv 5^2 \equiv 4 \pmod{7}$

また
$a\equiv b\pmod{p}$ なら $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$
$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$
も同時に示せる．

これまでの式を用いると

$\left(\frac{a}{p}\right) = (-1)^{\frac{p-1}{2}}$

というオイラーの規準が示すことができる．

こちらは
$a=g^i$ とすると $\left(\frac{a}{p}\right) = \left(\frac{g}{p}\right)^i = (-1)^i$
また
$a^{\frac{p-1}{2}} = \left(g^i\right)^{\frac{p-1}{2}} = \left(g^{\frac{p-1}{2}}\right)^i = (-1)^i$
となり，右辺と左辺は一致することがわかる．

平方剰余の相互法則

第一補充法則

$\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$

これはオイラーの規準において， $a=-1$ を代入することで導出できる．
この第一補充法則については，二平方和定理*1の証明に用いられる．

第二補充法則

$\left(\frac{2}{p}\right) = (-1)^{\frac{p^2 - 1}{8}}$

これはガウス和を用いて証明する方法がある．

ガウス和

$\zeta_n = e^{\frac{2\pi i}{n}}$ と表記するとき，奇素数 $p$ に対しガウス和を $\tau_p = \sum_{n=1}^{p-1}\left(\frac{n}{p}\right)\zeta_p^n$ と定義する．

ここで

$\bar{p}$ を $p,-p$ のうち，4を法として1と合同である方 $\bar{p}\equiv 1\pmod{4}$ とすると， $\tau_p^2 = \bar{p}$

が成り立つ．
ここで注意したいのは， $\bar{p} = (-1)^{\frac{p-1}{2}}$ とも書くことができるということ．第二補充法則の証明では用いないが，今後の平方剰余の相互法則で用いることとなる．

以下証明．
$\tau_p^2 = \left(\sum_{n=1}^{p-1}\left(\frac{n}{p}\right)\zeta^n_p\right) \left( \sum_{m=1}^{p-1}\left(\frac{m}{p}\right)\zeta^m_p\right)$
$= \sum_{n=1}^{p-1}\left( \sum_{m=1}^{p-1}\left(\frac{mn}{p}\right)\zeta^{m+n}_p\right)$

ここで整数 $t$ を用いて $n = mt$ と置換する． $m,2m,3m,\cdots,(p-1)m$ は $p$ を法として $1\sim p-1$ を並び替えたものになるのでこの置換は差し支えない．
（仮に同じモノが存在する $mt \equiv ms$ 場合， $m(t-s) \equiv 0$ となるが， $1\leq t-s,m < p$ なので．）

すると
$\tau_p^2 = \sum_{t=1}^{p-1}\left( \sum_{m=1}^{p-1}\left(\frac{m^2t}{p}\right)\zeta^{m(1+t)}_p\right)$
であり，明らかに $\left(\frac{m^2}{p}\right) = 1$ なので
$\tau_p^2 = \sum_{t=1}^{p-1}\left( \sum_{m=1}^{p-1}\left(\frac{t}{p}\right)\zeta^{m(1+t)}_p\right)$
となる．
$\tau_p^2 = \sum_{t=1}^{p-1}\left(\frac{t}{p}\right)\left( \sum_{m=1}^{p-1}\zeta^{m(1+t)}_p\right)$
と総和の中を整理する．

ここで $\sum_{m=1}^{p-1}\zeta^{m(1+t)}_p$ については等比数列の総和だが， $\zeta_n = e^{\frac{2\pi i}{n}}$ と定義しているので
$t\equiv -1\pmod{p}$ のとき $\zeta^{m(1+t)}_p=1$ になるため $\sum_{m=1}^{p-1}\zeta^{m(1+t)}_p = p-1$

$t\not\equiv -1 \pmod{p}$ のとき $\sum_{m=1}^{p-1}\zeta^{m(1+t)}_p = \frac{e^{\frac{2\pi i}{p}(1+t)} - e^{\frac{2\pi i}{p}p(1+t)}}{1-e^{\frac{2\pi i}{p}(1+t)}} = -1$
なので
$\tau_p^2 = \sum_{t=1}^{p-1}\left(\frac{t}{p}\right)\left( \sum_{m=1}^{p-1}\zeta^{m(1+t)}_p\right) = \left(\frac{-1}{p}\right)p - \sum_{t=1}^{p-1}\left(\frac{t}{p}\right)$

ここで $\sum_{t=1}^{p-1}\left(\frac{t}{p}\right)$ については，原始根 $g$ を用いると $g,g^2,g^3,\cdots,g^{p-1}$ は $1\sim p-1$ を並び替えたものであり，これに $g$ を乗じても同様に並び替えたものになる．
つまり
$\sum_{t=1}^{p-1}\left(\frac{t}{p}\right) = \sum_{t=1}^{p-1}\left(\frac{gt}{p}\right) = \left(\frac{g}{p}\right)\sum_{t=1}^{p-1}\left(\frac{t}{p}\right) = -\sum_{t=1}^{p-1}\left(\frac{t}{p}\right)$
なので
$\sum_{t=1}^{p-1}\left(\frac{t}{p}\right) = 0$

よって $\tau_p^2 = \left(\frac{-1}{p}\right)p$ となる．

ここで第一補充法則より $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$ なので命題が示せた．

第二補充法則の証明

$e^{\frac{2\pi i}{8}} = \frac{1+i}{\sqrt{2}}, e^{-\frac{2\pi i}{8}} = \frac{1-i}{\sqrt{2}}$ であることを利用する．ここで $\zeta_8 = \frac{1+i}{\sqrt{2}}$ と表記する．

オイラーの規準より $\left(\frac{2}{p}\right) = 2^{\frac{p-1}{2}}$
ここで $\zeta_8 + \zeta_8^{-1} = \sqrt{2}$ なので $\left(\frac{2}{p}\right) = (\zeta_8 + \zeta_8^{-1})^{p-1}$ と書ける．

また，二項定理より
$(\zeta_8 + \zeta_8^{-1})^p = \sum_{k=0}^{p}\binom{p}{k}\zeta_8^{2k-p}$
$(\zeta_8 + \zeta_8^{-1})^p = \zeta_8^p + \zeta_8^{-p} + \sum_{k=1}^{p-1}\binom{p}{k}\zeta_8^{2k-p}$
$(\zeta_8 + \zeta_8^{-1})^p = \zeta_8^p + \zeta_8^{-p} + \sum_{k=1}^{\frac{p-1}{2}}\binom{p}{k}(\zeta_8^{2k-p} + \zeta_8^{-(2k-p)})$

ここで $\zeta_8^n + \zeta_8^{-n}$ について．
$n$ を奇数に限定すると，
$\zeta_8 + \zeta_8^{-1} = \sqrt{2}$
$\zeta_8^3 + \zeta_8^{-3} = -\sqrt{2}$
$\zeta_8^5 + \zeta_8^{-5} = -\sqrt{2}$
$\zeta_8^7 + \zeta_8^{-7} = \sqrt{2}$
であり，この結果は $\zeta_8^n + \zeta_8^{-n} = (-1)^{\frac{n^2 - 1}{8}}\sqrt{2}$ と一致する．

これを用いると
$(\zeta_8 + \zeta_8^{-1})^p = (-1)^{\frac{p^2 - 1}{8}}\sqrt{2} + \sum_{k=1}^{\frac{p-1}{2}}\binom{p}{k}(-1)^{\frac{(2k-p)^2 - 1}{8}}\sqrt{2}$
であり，両辺を $\sqrt{2}$ で割ると
$(\zeta_8 + \zeta_8^{-1})^{p-1} = (-1)^{\frac{p^2 - 1}{8}} + \sum_{k=1}^{\frac{p-1}{2}}\binom{p}{k}(-1)^{\frac{(2k-p)^2 - 1}{8}}$
が得られる．

ここで $\binom{p}{k}$ は $p$ の倍数なので
$\left(\frac{2}{p}\right) = 2^{\frac{p-1}{2}} \equiv (-1)^{\frac{p^2 - 1}{8}} \pmod{p}$
であり，示すことができた．

平方剰余の相互法則

平方剰余の相互法則は

奇素数 $p,q$ に対し
$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$

であり，平方剰余の判定が結構楽になる．

以下この平方剰余の相互法則を示す．
$\left(\frac{\bar{q}}{p}\right) = \left(\frac{(-1)^{\frac{q-1}{2}}q}{p}\right) = \left(\frac{-1}{p}\right)^{\frac{q-1}{2}}\left(\frac{q}{p}\right)$
と変形し，第一補充法則より
$\left(\frac{\bar{q}}{p}\right) = (-1)^{\frac{q-1}{2}\cdot \frac{p-1}{2}}\left(\frac{q}{p}\right)$
が得られる．

両辺に $\left(\frac{q}{p}\right)$ をかけると
$\left(\frac{q}{p}\right)\left(\frac{\bar{q}}{p}\right) = (-1)^{\frac{q-1}{2}\cdot \frac{p-1}{2}}$
になり，
$\left(\frac{\bar{q}}{p}\right) = \left(\frac{p}{q}\right)$
を示すことができれば平方剰余の相互法則を示すことができる．

ここで $\tau_q^2 = \bar{q}$ なので， $\tau_q^{p-1} = (\bar{q})^{\frac{p-1}{2}}$ になるため，オイラーの規準より $\tau_q^{p-1} \equiv \left(\frac{\bar{q}}{p}\right)\pmod{p}$ になる．

ここでガウス和を $\tau_q = \sum_{n=1}^{q-1}\left(\frac{n}{q}\right)\zeta_q^n$ と定義しているので
$\tau_q^p = \left(\sum_{n_1=1}^{q-1}\left(\frac{n_1}{q}\right)\zeta_q^{n_1}\right)\left(\sum_{n_2=1}^{q-1}\left(\frac{n_2}{q}\right)\zeta_q^{n_2}\right)\cdots\left(\sum_{n_p=1}^{q-1}\left(\frac{n_p}{q}\right)\zeta_q^{n_p}\right)$
とする．
これをまとめると， $(n_1,n_2,\cdots,n_p)$ 全ての要素が $1\sim q-1$ を移動する集合を $A$ とし
$\tau_q^p = \sum_{A}\left(\frac{n_1n_2\cdots n_p}{q}\right)\zeta_q^{n_1+n_2+\cdots+n_p}$
と表記できる．
ここで $t$ を用いて，逆に $n_1+n_2+\cdots+n_p \equiv t \pmod{q}$ となる条件での集合 $A_t = (n_1,n_2,\cdots,n_p)$ についての和に置き換える．
$n_1+n_2+\cdots+n_p \equiv t \pmod{q}$ とおいたのは， $\zeta_q^q = 1$ であるため．
$t$ の取りうる値は $0\sim q-1$ なので，
$\tau_q^p = \sum_{t=0}^{q-1}\left(\sum_{A_t}\left(\frac{n_1n_2\cdots n_p}{q}\right)\right)\zeta_q^{t}$
となる．

ここで $\sum_{A_t}\left(\frac{n_1n_2\cdots n_p}{q}\right) = J_t$ と置換し，
$\tau_q^p = \sum_{t=0}^{q-1}J_t\zeta_q^{t}$
とまとめる．

ちなみに積について $J_{st} = \left(\frac{s}{q}\right)J_t$ となる．
実際 $st = (sn_1) + (sn_2) + \cdots + (sn_p)$ であるため，
$J_{st} = \sum_{A_t}\left(\frac{s^p \cdot n_1n_2\cdots n_p}{q}\right) = \left(\frac{s}{q}\right)^p\sum_{A_t}\left(\frac{n_1n_2\cdots n_p}{q}\right)$
ここで $p$ は素数なので
$J_{st} = \left(\frac{s}{q}\right)\sum_{A_t}\left(\frac{n_1n_2\cdots n_p}{q}\right) = \left(\frac{s}{q}\right)J_t$
が示せる．

ちなみに $\left(\frac{s}{q}\right) = -1$ となる $s$ をとると
$J_{st} = -J_t$
になるので， $J_0 = 0$ になる．

また， $J_t = \left(\frac{t}{q}\right)J_1$ なので
$\tau_q^p = \sum_{t=0}^{q-1}J_t\zeta_q^{t} = \sum_{t=1}^{q-1}\left(\frac{t}{q}\right)J_1\zeta_q^{t} = J_1\sum_{t=1}^{q-1}\left(\frac{t}{q}\right)\zeta_q^{t}$

ガウス和の定義 $\tau_q = \sum_{n=1}^{q-1}\left(\frac{n}{q}\right)\zeta_q^n$ より $\tau_q^p = J_1\tau_q$
$\therefore\tau_q^{p-1} = J_1$

$\sum_{A_t}\left(\frac{n_1n_2\cdots n_p}{q}\right) = J_t$ と置いていたので， $n_1+n_2+\cdots+n_p \equiv 1 \pmod{q}$ に関して
$\sum_{A_t}\left(\frac{n_1n_2\cdots n_p}{q}\right)$
を求めたい．

ちなみに $p$ と $q$ は互いに異なる素数なので $px \equiv 1 \pmod{q}$ になる $x$ が存在する．
その $x$ を $u$ と置換し， $n_1 = n_2 = \cdots = n_p = u$ と置くと
$\left(\frac{u^p}{q}\right) = \left(\frac{u}{q}\right)^p = \left(\frac{u}{q}\right)$
となる．

ここで原始根 $g$ を用いて $g^{k} \equiv u \pmod{q}$ ， $g^{l} \equiv p \pmod{q}$ とする．
また $g^{q-1}\equiv 1$ でもあり， $q$ は奇素数なので $q-1$ は偶数．
つまり
$pu = g^{kl} \equiv g^{m(q-1)}\equiv 1 \pmod{q}$
なので， $\left(\frac{p}{q}\right) = \left(\frac{u}{q}\right)$ となる．

よって $n_1 = n_2 = \cdots = n_p = u$ の場合は
$\sum_{A_t}\left(\frac{n_1n_2\cdots n_p}{q}\right) = \left(\frac{u^p}{q}\right) = \left(\frac{u}{q}\right)^p = \left(\frac{u}{q}\right)$
になる．

そうでない $n_1 + n_2 + \cdots + n_p \equiv t \pmod{q}$ の場合は，
$n_2 + n_3 + \cdots + n_p + n_1 \equiv t \pmod{q}$
と巡回させた場合全てに対しての総和を考える．
巡回させる場合の数は $p$ 通り存在する．
例えば3つの場合は
1,2,3
2,3,1
3,1,2
という感じになる．巡回させるだけなので3,2,1等の並び替えは考えない．

その巡回の場合はただ並び替えているだけなので $\left(\frac{n_1n_2\cdots n_p}{q}\right)$ の値は変わらない．
よって
$\sum_{k=1}^{p}\left(\frac{n_1n_2\cdots n_p}{q}\right) = p\left(\frac{n_1n_2\cdots n_p}{q}\right) \equiv 0\pmod{p}$
となり， $p$ の倍数になる．

以上を踏まえると
$J_1 \equiv \left(\frac{p}{q}\right)\pmod{p}$
となる．

これで
$\tau_q^{p-1} = J_1\equiv \left(\frac{p}{q}\right)\pmod{p}$
が示されたので
$\left(\frac{p}{q}\right) = \left(\frac{\bar{q}}{p}\right)$
が示された．

これでようやく平方剰余の相互法則

奇素数 $p,q$ に対し
$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$

を示すことができた．

平方剰余の相互法則の応用

例えば71を法として28は平方剰余か調べる．
$\left(\frac{28}{71}\right) = \left(\frac{2}{71}\right)^2\left(\frac{7}{71}\right) = \left(\frac{7}{71}\right)$
ここで平方剰余の相互法則を用いる．
$(-1) ^ {\frac{7-1}{2} \cdot \frac{71-1}{2}} = -1$
なので
$\left(\frac{28}{71}\right) = -\left(\frac{71}{7}\right) = -\left(\frac{1}{7}\right)$
ここで $1^2 \equiv 1 \pmod{7}$ なので $\left(\frac{1}{7}\right)=1$ になる．
つまり
$\left(\frac{28}{71}\right)= -1$
になるので71を法として28は平方剰余ではないという結論になる．

参考文献

素数と二次体の整数論
原始根定理の証明（青空学園）

*1:4で割って1余る素数は2つの平方数の和で表すことができるという定理