初等整数論/べき剰余

平方剰余

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

$a\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(\mathrm{mod}p)$ が解を持つのと ${\mathrm{I}\mathrm{n}\mathrm{d}}_{r}a$ が $(2,p-1)=2$ で割り切れるというのは同値である。したがって

$\left(\frac{a}{p}\right)=(-1{)}^{{\mathrm{I}\mathrm{n}\mathrm{d}}_{r}a}.$

定理 2.10

$a\equiv a^{\prime }(\mathrm{mod}p)$ ならば $\left(\frac{a}{p}\right)=\left(\frac{a^{\prime }}{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{)}^{{\mathrm{I}\mathrm{n}\mathrm{d}}_{r}abc\cdots }$

定理 2.3.4 より 、これは

$(-1{)}^{{\mathrm{I}\mathrm{n}\mathrm{d}}_{r}a+{\mathrm{I}\mathrm{n}\mathrm{d}}_{r}b+{\mathrm{I}\mathrm{n}\mathrm{d}}_{r}c+\cdots }(-1{)}^{{\mathrm{I}\mathrm{n}\mathrm{d}}_{r}a}(-1{)}^{{\mathrm{I}\mathrm{n}\mathrm{d}}_{r}b}=(-1{)}^{{\mathrm{I}\mathrm{n}\mathrm{d}}_{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}}(\mathrm{mod}p)$

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

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

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

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

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

$a^{\frac{p-1}{2}}\equiv ̸1(\mathrm{mod}p).$ このときフェルマーの小定理より

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

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

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

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

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

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

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

$\equiv a^{\frac{p-3}{2}}(\mathrm{mod}p)$

であるから、

$\begin{array}{cc}(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}}(\mathrm{mod}p).\\ \end{array}$

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

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

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

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

• $\left(\frac{a}{p}\right)=1\Rightarrow a^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$
• $\left(\frac{a}{p}\right)=-1\Rightarrow a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}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(\mathrm{mod}p)$ に解がある $⟺p\equiv 1(\mathrm{mod}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(\mathrm{mod}p)$ に解がある $⟺p\equiv 1,7(\mathrm{mod}8).$

証明
2 から証明する。

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

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

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

ガウスの補題

$\gcd (a,p)=1$ のとき、$A=\{a,2a,3a,\cdots ,\frac{p-1}{2}a\}$ をそれぞれ $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\ne y)$ について、

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

$\{1,2,3,\cdots ,\frac{p-1}{2}\}$ に合同で、そのうち負の数の個数が $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(\mathrm{mod}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{array}{c}1(p\equiv 1,4(\mathrm{mod}5)),\\ -1(p\equiv 2,3(\mathrm{mod}5))\end{array}$

が成り立つ。