初等整数論/べき剰余

平方剰余

$p$ を奇素数、$a$ を $p$ で割り切れない数、$x^{2}\equiv a{\pmod {p}}$ としたときに解を持つ、持たないにしたがって $a$ を $p$ の平方剰余、平方非剰余 という。

$a\not \equiv 0$ のとき $a$ が平方剰余、非剰余にしたがって

$\left({\frac {a}{p}}\right)=1,\,-1$ とする。また、便宜上 $\left({\frac {kp}{p}}\right)=0$ とする。これをルジャンドル記号と呼ぶ。

したがって $\left({\frac {a}{p}}\right)$ は $a$ の属する剰余類にのみ依存する。そして $\left({\frac {a}{p}}\right)=-1$ ならば $kp+a$ の形の平方数は存在しない。

例 $\left({\frac {2}{3}}\right)=\left({\frac {3}{4}}\right)=\left({\frac {3}{5}}\right)=-1,\left({\frac {4}{5}}\right)=1$ である。

補題 1 $r$ を $p$ の原始根とする。定理 2.3.4 から $x^{2}\equiv a{\pmod {p}}$ が解を持つのと ${\rm {Ind}}_{r}\,a$ が $(2,p-1)=2$ で割り切れるというのは同値である。したがって

$\left({\frac {a}{p}}\right)=(-1)^{{\rm {Ind}}_{r}\,a}.$

定理 2.10

$a\equiv a'{\pmod {p}}$ ならば $\left({\frac {a}{p}}\right)=\left({\frac {a'}{p}}\right)$

証明
合同の推移性、または補題 1 によって明白。

定理 2.11

$\left({\frac {abc\cdots }{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)\left({\frac {c}{p}}\right)\cdots$

証明
補題 1 より $\left({\frac {abc\cdots }{p}}\right)=(-1)^{{\rm {Ind}}_{r}\,abc\cdots }$

定理 2.3.4 より 、これは

$(-1)^{{\rm {Ind}}_{r}\,a\ +{\rm {Ind}}_{r}\ b\ +{\rm {Ind}}_{r}\,c\ +\cdots }(-1)^{{\rm {Ind}}_{r}\,a}\ (-1)^{{\rm {Ind}}_{r}\,b}\ =(-1)^{{\rm {Ind}}_{r}\,c}\cdots$

に等しい。ここで再び補題 1 より、これは

$=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)\left({\frac {c}{p}}\right)\cdots$

に等しい。

定理 2.12 (オイラーの規準)

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

証明 1
定理 2.3.4 から $x^{2}\equiv a{\pmod {p}}$ が解を持つ、つまり $\left({\frac {a}{p}}\right)=1$ のとき、

$f={\frac {p-1}{(2,p-1)}},\ \ a^{f}\equiv 1{\pmod {p}}.$

ここで、$(2,p-1)=2$ より、$a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$

したがって $\left({\frac {a}{p}}\right)\equiv 1{\pmod {p}}.$

逆に $\left({\frac {a}{p}}\right)=-1$ 、つまり $x^{2}\equiv a{\pmod {p}}$ が解を持たないとき、再び定理 2.3.4 から

$a^{\frac {p-1}{2}}\not \equiv 1{\pmod {p}}.$ このときフェルマーの小定理より

$(a^{\frac {p-1}{2}})^{2}=a^{p-1}\equiv 1{\pmod {p}}.$

よって $a^{\frac {p-1}{2}}\equiv -1\equiv \left({\frac {a}{p}}\right){\pmod {p}}.$

以上より定理は証明される。

証明 2
定理 1.8 より、$A=\{0,a,2a,\cdots ,(p-1)a\}$ は剰余系をなすので、この中の任意の数 $r$ について $rs\equiv a{\pmod {p}}$ となる $s\in A$ がただ一つ存在する。これを $r$ の配偶と呼ぶことにする。

ここで $\left({\frac {a}{p}}\right)=1$ のとき $r$ を $x^{2}\equiv a{\pmod {p}}$ の解とすれば、$r$ の配偶はそれ自身である。また、

$(p-r)^{2}=p^{2}-2pr+r^{2}\equiv r^{2}{\pmod {p}}$ より $p-r$ も方程式の解である。このとき $r=p-r$ とすると $p=2r$ となり、奇素数であるという仮定に反する。したがって $r\neq p-r.$

合同方程式の基本定理から、上の方程式の解を満たすもの、すなわち配偶が自身であるものは $r,p-r$ の2つであり、他の $p-3$ 個の数は2個ずつ配偶があって、それらの積は

$\equiv a^{\frac {p-3}{2}}{\pmod {p}}$

であるから、

${\begin{aligned}(p-1)!&\equiv r\cdot (p-r)\cdot a^{\frac {p-3}{2}}\\&\equiv -r^{2}\cdot a^{\frac {p-3}{2}}\\&\equiv -a\cdot a^{\frac {p-3}{2}}=-a^{\frac {p-1}{2}}{\pmod {p}}.\\\end{aligned}}$

以上より $\left({\frac {a}{p}}\right)=1\Rightarrow (p-1)!\equiv -a^{\frac {p-1}{2}}{\pmod {p}}$

次に $\left({\frac {a}{p}}\right)=-1$ のときは上の $r,p-r$ のような数はないので配偶が ${\frac {p-1}{2}}$ ペアできて

$(p-1)!\equiv a^{\frac {p-1}{2}}{\pmod {p}}$

$a=1$ は自明に前に属すので $(p-1)!\equiv -1{\pmod {p}}$（すなわちウィルソンの定理）。したがって、

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

これがオイラーの規準である。

平方剰余の相互法則

$p,q$ を相異なる奇素数としたときに

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

2, 3 をそれぞれ第一補充法則、第二補充法則という。まずはそれぞれの意味を説明する。

1 は、$p,q$ のどちらかが $4n+1$ の形のとき $\left({\frac {p}{q}}\right)=\left({\frac {q}{p}}\right)$ で、どちらとも $4n+3$ の形のときに限り $\left({\frac {p}{q}}\right)=-\left({\frac {q}{p}}\right)$ である、という意味である。

2 は、$x^{2}\equiv -1{\pmod {p}}$ に解がある $\iff p\equiv 1{\pmod {4}}$

3 は、$p=8n+1,\,8n+7$ のとき $\left({\frac {p}{q}}\right)=1$ で、$p=8n+3,\,8n+5$ のとき $\left({\frac {p}{q}}\right)=-1$ である。つまり $x^{2}\equiv 2{\pmod {p}}$ に解がある $\iff p\equiv 1,7{\pmod {8}}.$

証明
2 から証明する。

オイラーの規準より、$\left({\frac {-1}{p}}\right)\equiv (-1)^{\frac {p-1}{2}}{\pmod {p}}.$

どちらも $\pm 1$ の値を取り、$p$ は奇素数なので $\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}.$

さて、3 であるが、これにはガウスの補題を用いる。

ガウスの補題

$\gcd(a,p)=1$ のとき、$A=\left\{a,2a,3a,\cdots ,{\frac {p-1}{2}}a\right\}$ をそれぞれ $p$ で割ったときの余りが ${\frac {p}{2}}$ より大きい数が $n$ 個あったとき、

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

証明
ある数を $p$ で割った余りが ${\frac {p}{2}}$ よりも大きいならば、それから $p$ を引くと $-{\frac {p}{2}}$ よりも大きい負の余りを得る。つまり、絶対最小剰余である。上の $n$ というのは負の絶対最小剰余の個数である。

$A$ の任意の2つの数 $ax,ay\ (x\neq y)$ について、

$(a,p)=1,\ {\frac {1-p}{2}}\leqq x\pm y\leqq {\frac {p+1}{2}}$ であり、$x\pm y\neq 0$ より、$A$ の中には絶対最小剰余として等しいもの、また絶対最小剰余として符号が逆なものも存在しない。すなわち全体として符号を無視すれば

$\left\{1,2,3,\cdots ,{\frac {p-1}{2}}\right\}$ に合同で、そのうち負の数の個数が $n$ である。したがって

$a\cdot 2a\cdot 3a\cdots {\frac {p-1}{2}}a\equiv (-1)^{n}\cdot 1\cdot 2\cdot 3\cdots {\frac {p-1}{2}}$

だが、 1, 2, ..., ${\frac {p-1}{2}}$ はいずれも $p$ と互いに素なので

$a^{\frac {p-1}{2}}\equiv (-1)^{n}$

を得る。オイラーの規準によって

$\left({\frac {a}{p}}\right)\equiv (-1)^{n}{\pmod {p}}.$

どちらも $\pm 1$ に等しく、$p$ は奇素数なので

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

さて 3 の証明だが、

$2,4,6,\cdots ,p-1$

の中で ${\frac {p}{2}}$ より多いものの個数が $n$ である。

(i) $p=8n+1$ のとき

${\frac {p}{2}}=4n+{\frac {1}{2}},\ p-1=8n$ なので、この間にある偶数の数は ${\frac {8n-4n}{2}}=2n$ であり、$\left({\frac {2}{p}}\right)=(-1)^{2n}=1$

また ${\frac {p^{2}-1}{8}}=8n^{2}+2n$ より、$(-1)^{\frac {p^{2}-1}{8}}=1$ で、

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

(ii) $p=8n+3$ のとき

${\frac {p}{2}}=4n+{\frac {3}{2}},\ p-1=8n+2$ なので、この間にある偶数の数は ${\frac {(8n+2)-(4n+2)}{2}}+1=2n+1$ であり、$\left({\frac {2}{p}}\right)=(-1)^{2n+1}=-1.$

また ${\frac {p^{2}-1}{2}}=8n^{2}+6n+1$ より、$(-1)^{\frac {p^{2}-1}{8}}=-1$ で、

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

(iii) $p=8n+5$ のとき

${\frac {p}{2}}=4n+{\frac {5}{2}},\ p-1=8n+4$ なので、この間にある偶数の数は ${\frac {(8n+4)-(4n+2)}{2}}=2n+1$ であり、$\left({\frac {2}{p}}\right)=(-1)^{2n+1}=-1.$

また ${\frac {p^{2}-1}{2}}=8n^{2}+10n+3$ より、$(-1)^{\frac {p^{2}-1}{8}}=-1$ で、

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

(iv) $p=8n+7$ のとき

${\frac {p}{2}}=4n+{\frac {7}{2}},\ p-1=8n+6$ なので、この間にある偶数の数は ${\frac {(8n+4)-(4n+4)}{2}}=2n$ であり、$\left({\frac {2}{p}}\right)=(-1)^{2n}=-1.$

また ${\frac {p^{2}-1}{2}}=8n^{2}+14n+3$ より、$(-1)^{\frac {p^{2}-1}{8}}=-1$ で、

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

以上により 3 が証明される。

最後に相互法則であるが、初等整数論/平方剰余の相互法則の証明に譲る。

例 1 $\left({\frac {31}{103}}\right)$ を求めよ。

相互法則より

$\left({\frac {31}{103}}\right)=(-1)^{15\cdot 51}\left({\frac {103}{31}}\right)=-\left({\frac {10}{31}}\right)=-\left({\frac {2}{31}}\right)\left({\frac {5}{31}}\right)$

となる。ここで、第二補充法則と相互法則を用いて

$\left({\frac {2}{31}}\right)=1,\left({\frac {5}{31}}\right)=\left({\frac {31}{5}}\right)=\left({\frac {1}{5}}\right)=1$

を得るから

$\left({\frac {31}{103}}\right)=-1$

とわかる。

例 2 $p$ が奇素数のとき

$\left({\frac {5}{p}}\right)=\left({\frac {p}{5}}\right)={\begin{cases}1(p\equiv 1,4{\pmod {5}}),\\-1(p\equiv 2,3{\pmod {5}})\end{cases}}$

が成り立つ。