次: 整数を平方数の和に分解すること 上: 平方剰余 前: 平方剰余

平方剰余とルジャンドルの記号

5を法とする剰余類は $0,\ 1,\ 2,\ 3,\ 4$ であるが，それらの類の数を平方すると剰余類は順に

$$0,\ 1^2=1,\ 2^2=4,\ 3^2\equiv 4\quad (\bmod.\ 5),\ 4^2\equiv 1\quad (\bmod.\ 5)$$

となり，2や3は平方数を5を法とする剰余の中には登場しない． 1や4は5の平方剰余，2や3は平方非剰余という．

ある整数$a$が整数$b$を法として平方剰余であるか平方非剰余であるかということと，整数$b$が整数$a$を法として平方剰余であるか平方非剰余であるかということとの間にはガウスが整数論の基本定理と呼んだ大変美しい定理が成り立つ． それが 平方剰余の相互法則 である． これはこの『数論初歩』全体でもいちばん山場の定理である．

ぜひ高校生に「平方剰余の相互法則」を理解しその美しさを味わってもらいた

平方剰余

素数5に比べて素数2は特異である． 2で割った数の剰余類は $0,\ 1$ である．それらの類の数を平方すると剰余類 $0,\ 1$ となり変わらない．

以下本節では $p$ は2以外の素数とする． $x^2\equiv a\quad (\bmod.\ p)$ が解をもつとき $a$ を $p$ の平方剰余， 解がないとき平方非剰余という． $a\not \equiv 0\quad (\bmod.\ p)$ である整数 $a$ に対して $a$ が $p$ の平方剰余であるか非剰余であるかにしたがって

$$\left(\dfrac{a}{p} \right)=+1\quad または\quad -1$$

とする．これをルジャンドル(Legendre)の記号という．

$p$ の任意の原始根を底として指数をとるとき，前節の議論から $\Ind.\,a$ が偶数なら $a$ は平方剰余，奇数なら非剰余であった．ゆえに

$$\left(\dfrac{a}{p} \right)=(-1)^{\Ind.\,a}$$ (3.1)

ゆえに $p$ に関する $p-1$ 個の既約類の中で半数は平方剰余のみからなり， 半数は非剰余のみからなる． $x^2\equiv (p-x)^2\quad (\bmod.\ p)$ なので $1,\ 2,\ \cdots,\ \dfrac{p-1}{2}$ の 平方が平方剰余のすべてである． また(3.1)から次の2性質が成り立つ．

1. $a\equiv a'\quad (\bmod.\ p)$ ならば $\left(\dfrac{a}{p} \right)=\left(\dfrac{a'}{p} \right)$
2. $\left(\dfrac{abc \cdots}{p} \right) =\left(\dfrac{a}{p} \right)\left(\dfrac{b}{p} \right)\left(\dfrac{c}{p} \right) \cdots$

これは例えば

$$(非剰余数)\times(非剰余数)=(剰余数),\ \quad (剰余数)\times(非剰余数)=(非剰余数)$$

ということである． 実際$p=5$ のとき

$$2\times3\equiv 1\quad (\bmod.\ 5),\ \quad 4\times 2\equiv 3\quad (\bmod.\ 5)$$

である．

定理 31 (オイラーの規準)
3以上の素数$p$と整数$a$に対して

$$\left(\dfrac{a}{p} \right)\equiv a^{\frac{p-1}{2}}\quad (\bmod.\ p)$$

が成り立つ．■

証明     $a$ が平方剰余であるための必要十分条件は 定理30から

$$a^{ \frac{p-1}{2}}\equiv 1\quad (\bmod.\ p)$$

である．

ゆえに $\left(\dfrac{a}{p} \right)=1$ ならば， $a^{ \frac{p-1}{2}}\equiv 1\quad (\bmod.\ p)$ で一致．

また $\left(\dfrac{a}{p} \right)=-1$ ならば， $a^{ \frac{p-1}{2}}\not\equiv 1\quad (\bmod.\ p)$ ． ところがフェルマの小定理から $\left(a^{ \frac{p-1}{2}}\right)^2\equiv 1\quad (\bmod.\ p)$ ． したがって $a^{ \frac{p-1}{2}}\equiv -1\quad (\bmod.\ p)$ でやはり一致する．□

この証明は，これまでの結果を結びつけただけであるが，より直接的な証明がディリクレの 『整数論講義』にある.『初等整数論講義』に従ってそれを紹介する．

ディリクレの別証明

$a$ を $p$ で割り切れない数とし，集合 $A$ を

$$A=\{\ 1,\ 2,\ 3,\ \cdots,\ p-1\ \}$$

とする． $A$ の任意の元 $r$ に対して

$$rs\equiv a\quad (\bmod.\ p)$$

となる $A$ の元$s$ がただ一つ存在する．この $s$ を $r$ の「共役」と呼ぼう．

$\left(\dfrac{a}{p} \right)=1$ のとき． $r$ を $x^2\equiv a\quad (\bmod.\ p)$ の解とすれば, $r$ の共役は$r$ 自身である． $p-r$ もまた $x^2\equiv a\quad (\bmod.\ p)$ の解で, $p-r$ の共役も$p-r$ である． $A$ の元で $x^2\equiv a\quad (\bmod.\ p)$ を満たすものは定理14から この二つ( $p$ が奇数なので$p\ne p-r$ )にかぎる．この二つを除いた殘りの $p-3$ 個は 二つずつ互いに共役で，それら $p-3$ 個の積は， $\equiv a^{ \frac{p-3}{2}}\quad (\bmod.\ p)$ となる． $r(p-r)\equiv -r^2\equiv -a\quad (\bmod.\ p)$ なので

$$\left(\dfrac{a}{p} \right)=1 \Rightarrow (p-1)!\equiv -a^{ \frac{p-1}{2}}\quad (\bmod.\ p)$$

$\left(\dfrac{a}{p} \right)=-1$のときは共役と一致する数は $A$ にないので

$$\left(\dfrac{a}{p} \right)=-1 \Rightarrow (p-1)!\equiv a^{ \frac{p-1}{2}}\quad (\bmod.\ p)$$

とくに $\left(\dfrac{1}{p} \right)=1$ なので

$$(p-1)!\equiv -1\quad (\bmod.\ p)$$

これはウイルソンの定理といわれているものである．

これをあわせると上記の場合分けは

$$\left. \begin{array}{l} \left(\dfrac{a}{p} \right)=1 ... ...}{2}}\equiv -1 \end{array} \right\} \quad (\bmod.\ p)．$$

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

注意 3.1.1        この証明ではフェルマの小定理を用いていない． $\left(\dfrac{a}{p} \right)=\pm1$ にかかわらず，

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

つまりこれはフェルマの小定理の別証になっている．

例 3.1.1        $p=5$ のとき．

$$2^1\equiv 2,\ 2^2\equiv 4,\ 2^3\equiv 3,\ 2^4\equiv 1\ \quad (\bmod.\ 5)$$

であるから，2は法5に関する原始根であり，

$$\left(\dfrac{1}{5} \right)=1,\ \left(\dfrac{2}{5} \right)=-... ... \left(\dfrac{3}{5} \right)=-1,\ \left(\dfrac{4}{5} \right)=1$$

一方． $\dfrac{p-1}{2}=2$なのでオイラーの規準から

$$\left(\dfrac{1}{5} \right)\equiv 1,\ \left(\dfrac{2}{5} \ri... ...\left(\dfrac{4}{5} \right)\equiv 4^2\equiv 1\quad (\bmod.\ 5)$$

となる．

次: 整数を平方数の和に分解すること 上: 平方剰余 前: 平方剰余