平方剰余の相互法則(1) - エレファント・ビジュアライザー調査記録

以前別のところで書いたことがあるものですがここにも書いておきます。

【平方剰余】

ある整数 $x$ の平方を整数 $a$ で割ったときの余りが $b$ であるとき、 $b$ を法 $a$ に関する平方剰余といいます。

【ルジャンドルの記号】

$b$ が法 $a$ に関する平方剰余であるとき $\left(\cfrac{b}{a}\right) = 1$
$b$ が法 $a$ に関する平方剰余ではないとき $\left(\cfrac{b}{a}\right) = -1$

と $\left(\cfrac{b}{a}\right)$ を定義します。

この記法を拡張したものもあるようなので書いておきます。奇素数 $a$ と整数 $b$ に対して

$b$ が $a$ の倍数ではなく、ある整数 $x$ に対して $x^2 \equiv b \ (\mathrm{mod} \ a)$ であるとき $\left(\cfrac{b}{a}\right) = 1$
$b$ が $a$ の倍数ではなく、任意の整数 $x$ に対して $x^2 \not \equiv b \ (\mathrm{mod} \ a)$ であるとき $\left(\cfrac{b}{a}\right) = -1$
$b$ が $a$ の倍数であるとき $\left(\cfrac{b}{a}\right) = 0$

と定義します。

【平方剰余の相互法則】

$p$ , $q$ が $2$ ではない素数のとき、( $p$ , $q$ は奇数なので、 $4$ で割ると $1$ 余るか $3$ 余るかのどちらかとなります)

$p$ を $4$ で割ると $1$ 余るか、または、 $q$ を $4$ で割ると $1$ 余るときは、 $\left(\cfrac{p}{q}\right) = \left(\cfrac{q}{p}\right)$
$p$ を $4$ で割ると $3$ 余り、かつ、 $q$ を $4$ で割ると $3$ 余るときは、 $\left(\cfrac{p}{q}\right) = -\left(\cfrac{q}{p}\right)$

が成り立ちます。これを平方剰余の相互法則といいます。

以下の表は縦に $p$ 、横に $q$ をとったとき q が法 p に関する平方剰余のとき●、そうでないとき○とした表です。

0003	○	○	●	○	●	○	●	○	○	●	●	○	●	○
0005	○	○	○	●	○	○	●	○	●	●	○	●	○	○
0007	○	○	○	●	○	○	○	●	●	○	●	○	●	○
0011	●	●	○	○	○	○	○	●	○	●	●	○	○	●
0013	●	○	○	○	○	●	○	●	●	○	○	○	●	○
0017	○	○	○	○	●	○	●	○	○	○	○	○	●	●
0019	○	●	●	●	○	●	○	●	○	○	○	○	●	●
0023	●	○	○	○	●	○	○	○	●	●	○	●	○	●
0029	○	●	●	○	●	○	○	●	○	○	○	○	○	○
0031	○	●	●	○	○	○	●	○	○	○	○	●	○	●
0037	●	○	●	●	○	○	○	○	○	○	○	●	○	●
0041	○	●	○	○	○	○	○	●	○	●	●	○	●	○
0043	○	○	○	●	●	●	○	●	○	●	○	●	○	●
0047	●	○	●	○	○	●	○	○	○	○	●	○	○	○

$p$ を $4$ で割ると $3$ 余り、かつ、 $q$ を $4$ で割ると $3$ 余るときに対角線より右上の部分の●と○を入れ替えたら、以下のように対角線に関して対称になります。

0003	○	○	○	●	●	○	○	●	○	○	●	○	○	●
0005	○	○	○	●	○	○	●	○	●	●	○	●	○	○
0007	○	○	○	○	○	○	●	○	●	●	●	○	○	●
0011	●	●	○	○	○	○	●	○	○	○	●	○	●	○
0013	●	○	○	○	○	●	○	●	●	○	○	○	●	○
0017	○	○	○	○	●	○	●	○	○	○	○	○	●	●
0019	○	●	●	●	○	●	○	○	○	●	○	○	○	○
0023	●	○	○	○	●	○	○	○	●	○	○	●	●	○
0029	○	●	●	○	●	○	○	●	○	○	○	○	○	○
0031	○	●	●	○	○	○	●	○	○	○	○	●	●	○
0037	●	○	●	●	○	○	○	○	○	○	○	●	○	●
0041	○	●	○	○	○	○	○	●	○	●	●	○	●	○
0043	○	○	○	●	●	●	○	●	○	●	○	●	○	○
0047	●	○	●	○	○	●	○	○	○	○	●	○	○	○

以下の表は縦に $p$ 、横に $a = 1, 2, 3, …$ をとったとき $a$ が法 $p$ に関する平方剰余のとき●、そうでないとき○とした表です。

0003	●○
0005	●○○●
0007	●●○●○○
0011	●○●●●○○○●○
0013	●○●●○○○○●●○●
0017	●●○●○○○●●○○○●○●●
0019	●○○●●●●○●○●○○○○●●○
0023	●●●●○●○●●○○●●○○●○●○○○○
0029	●○○●●●●○●○○○●○○●○○○●○●●●●○○●
0031	●●○●●○●●●●○○○●○●○●●●○○○○●○○●○○
0037	●○●●○○●○●●●●○○○●○○○○●○○○●●●●○●○○●●○●
0041	●●○●●○○●●●○○○○○●○●○●●○●○●○○○○○●●●○○●●○●●
0043	●○○●○●○○●●●○●●●●●○○○●○●●●○○○○○●○○○●●○●○●●○
0047	●●●●○●●●●○○●○●○●●●○○●○○●●○●●○○○●○●○●●○○○○●○○○○

$p$ を $4$ で割ると $3$ 余るときに中央より右の部分の●と○を入れ替えたら、以下のように左右対称になります。

0003																							●	●
0005																						●	○	○	●
0007																					●	●	○	○	●	●
0011																			●	○	●	●	●	●	●	●	○	●
0013																		●	○	●	●	○	○	○	○	●	●	○	●
0017																●	●	○	●	○	○	○	●	●	○	○	○	●	○	●	●
0019															●	○	○	●	●	●	●	○	●	●	○	●	●	●	●	○	○	●
0023													●	●	●	●	○	●	○	●	●	○	○	○	○	●	●	○	●	○	●	●	●	●
0029										●	○	○	●	●	●	●	○	●	○	○	○	●	○	○	●	○	○	○	●	○	●	●	●	●	○	○	●
0031									●	●	○	●	●	○	●	●	●	●	○	○	○	●	○	○	●	○	○	○	●	●	●	●	○	●	●	○	●	●
0037						●	○	●	●	○	○	●	○	●	●	●	●	○	○	○	●	○	○	○	○	●	○	○	○	●	●	●	●	○	●	○	○	●	●	○	●
0041				●	●	○	●	●	○	○	●	●	●	○	○	○	○	○	●	○	●	○	●	●	○	●	○	●	○	○	○	○	○	●	●	●	○	○	●	●	○	●	●
0043			●	○	○	●	○	●	○	○	●	●	●	○	●	●	●	●	●	○	○	○	●	●	○	○	○	●	●	●	●	●	○	●	●	●	○	○	●	○	●	○	○	●
0047	●	●	●	●	○	●	●	●	●	○	○	●	○	●	○	●	●	●	○	○	●	○	○	○	○	●	○	○	●	●	●	○	●	○	●	○	○	●	●	●	●	○	●	●	●	●

【平方剰余の相互法則・第1補充法則】

$p$ が $2$ ではない素数のとき、( $p$ は奇数なので、 $4$ で割ると $1$ 余るか $3$ 余るかのどちらかとなります)

$p$ を $4$ で割ると $1$ 余るときは、 $-1$ は法 $p$ に関する平方剰余であり、
$p$ を $4$ で割ると $3$ 余るときは、 $-1$ は法 $p$ に関する平方剰余ではありません。

以下の表は縦に $p$ をとったとき $-1$ が法 $p$ に関する平方剰余のとき■、そうでないとき□としたものを1列目に、 $p$ を $4$ で割ると $3$ 余るときは、■と□を入れ替えたものを2列目に書いたものです。

0003	□	■
0005	■	■
0007	□	■
0011	□	■
0013	■	■
0017	■	■
0019	□	■
0023	□	■
0029	■	■
0031	□	■
0037	■	■
0041	■	■
0043	□	■
0047	□	■

【平方剰余の相互法則・第2補充法則】

$p$ が $2$ ではない素数のとき、( $p$ は奇数なので、 $8$ で割ると余りは $1$ , $3$ , $5$ , $7$ のどれかになります)

$p$ を $8$ で割ると $1$ または $7$ 余るときは、 $2$ は法 $p$ に関する平方剰余であり、
$p$ を $4$ で割ると $3$ または $5$ 余るときは、 $2$ は法 $p$ に関する平方剰余ではありません。

以下の表は縦に $p$ をとったとき $2$ が法 $p$ に関する平方剰余のとき■、そうでないとき□としたものを1列目に、 $p$ を $8$ で割ると $1$ または $7$ 余るときは、■と□を入れ替えたものを2列目に書いたものです。

0003	□	■
0005	□	■
0007	■	■
0011	□	■
0013	□	■
0017	■	■
0019	□	■
0023	■	■
0029	□	■
0031	■	■
0037	□	■
0041	■	■
0043	□	■
0047	■	■

【オイラーの規準】

$p$ が $2$ ではない素数、 $a$ が $p$ と素な整数のとき、

$a$ が法 $p$ に関する平方剰余のとき、 $a$ の $(p-1)/2$ 乗を $p$ で割ったときの余りは $1$ 、
$a$ が法 $p$ に関する平方剰余ではないとき、 $a$ の $(p-1)/2$ 乗を $p$ で割ったときの余りは $p-1$ になります。

以下の表は縦に $p$ 、横に $a = 1, 2, 3, …$ をとったとき $a$ の $(p-1)/2$ 乗を $p$ で割ったときの余りが $1$ のとき■、 $-1$ のとき□とした表です。

0003	■□
0005	■□□■
0007	■■□■□□
0011	■□■■■□□□■□
0013	■□■■□□□□■■□■
0017	■■□■□□□■■□□□■□■■
0019	■□□■■■■□■□■□□□□■■□
0023	■■■■□■□■■□□■■□□■□■□□□□
0029	■□□■■■■□■□□□■□□■□□□■□■■■■□□■
0031	■■□■■□■■■■□□□■□■□■■■□□□□■□□■□□
0037	■□■■□□■□■■■■□□□■□□□□■□□□■■■■□■□□■■□■
0041	■■□■■□□■■■□□□□□■□■□■■□■□■□□□□□■■■□□■■□■■
0043	■□□■□■□□■■■□■■■■■□□□■□■■■□□□□□■□□□■■□■□■■□
0047	■■■■□■■■■□□■□■□■■■□□■□□■■□■■□□□■□■□■■□□□□■□□□□