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

【平方剰余の相互法則】

$p$ , $q$ が $2$ ではない異なる素数のとき、 $\left(\cfrac{q}{p}\right) \left(\cfrac{p}{q}\right) = (-1)^{ \frac{(p-1)(q-1)}{4} }$
が成り立ちます。

[証明]
「平方剰余の相互法則ガウスの全証明」Vに従って証明します。 $0$ から $pq - 1$ までの数 $a$ を以下のように $p×q$ の長方形の形に並べます。

[1] 縦 $x$ , 横 $y$ の位置には、 $a$ を $p$ で割った余りが $x$ 、 $a$ を $q$ で割った余りが $y$ であるような $a$ が来るようにします。Chinese Remainder Theoremにより、このような並べ方はできます。
[2] 先に横方向に $0, 1, 2, …$ と並べます(縦 $x$ , 横 $y$ の位置には $qx + y$ )。
[3] 先に縦方向に $0, 1, 2, …$ と並べます(縦 $x$ , 横 $y$ の位置には $py + x$ )。

$p=11$ , $q=7$ のときは以下の図のようになります。
[1]

0000	00	56	35	14	70	49	28	07	63	42	21
0001	22	01	57	36	15	71	50	29	08	64	43
0002	44	23	02	58	37	16	72	51	30	09	65
0003	66	45	24	03	59	38	17	73	52	31	10
0004	11	67	46	25	04	60	39	18	74	53	32
0005	33	12	68	47	26	05	61	40	19	75	54
0006	55	34	13	69	48	27	06	62	41	20	76

[2]

0000	00	01	02	03	04	05	06	07	08	09	10
0001	11	12	13	14	15	16	17	18	19	20	21
0002	22	23	24	25	26	27	28	29	30	31	32
0003	33	34	35	36	37	38	39	40	41	42	43
0004	44	45	46	47	48	49	50	51	52	53	54
0005	55	56	57	58	59	60	61	62	63	64	65
0006	66	67	68	69	70	71	72	73	74	75	76

[3]

0000	00	07	14	21	28	35	42	49	56	63	70
0001	01	08	15	22	29	36	43	50	57	64	71
0002	02	09	16	23	30	37	44	51	58	65	72
0003	03	10	17	24	31	38	45	52	59	66	73
0004	04	11	18	25	32	39	46	53	60	67	74
0005	05	12	19	26	33	40	47	54	61	68	75
0006	06	13	20	27	34	41	48	55	62	69	76

$0$ 以外の $1$ から $pq - 1$ までの数 $a$ を以下のように分類します。

■

▲

●

□

△

○

(*1)

＋

－

(*2)

０

＋

－

０

＋

－

(*3)

＋

－

０

＋

－

０

＋

－

＋

－

０

＋

－

０

＋

－

(*1) ＋は $0 < a < \cfrac{pq}{2}$ のとき、－は $a > \cfrac{pq}{2}$ のとき
(*2) ＋は $0 < a \ \mathrm{mod} \ p < \cfrac{p}{2}$ のとき、－は $a \ \mathrm{mod} \ p > \cfrac{p}{2}$ のとき、０は $a \ \mathrm{mod} \ p = 0$ のとき
(*3) ＋は $0 < a \ \mathrm{mod} \ q < \cfrac{q}{2}$ のとき、－は $a \ \mathrm{mod} \ q > \cfrac{q}{2}$ のとき、０は $a \ \mathrm{mod} \ q = 0$ のとき

$a \ \mathrm{mod} \ p$ は $x$ を $p$ で割った余りを表します( $a≡b \ ( \mathrm{mod} \ p)$ となる $b$ のうちで $0$ か正の数の中で最小のもの)。
[1]

0000	×	α	■	■	α	α	Α	Α	□	□	Α
0001	▲	●	ε	●	●	ε	δ	Γ	Γ	δ	δ
0002	β	●	●	ε	●	●	δ	δ	Γ	Γ	δ
0003	β	ε	●	●	ε	●	Γ	δ	δ	Γ	Γ
0004	Β	γ	γ	Δ	Δ	γ	○	Ε	○	○	Ε
0005	Β	Δ	γ	γ	Δ	Δ	○	○	Ε	○	○
0006	△	Δ	Δ	γ	γ	Δ	Ε	○	○	Ε	○

[1]の図より

■の個数 = □の個数 (図では 2)
Αの個数 = αの個数 (図では 3) (これを $a$ とおきます)
▲の個数 = △の個数 (図では 1)
Βの個数 = βの個数 (図では 2) (これを $b$ とおきます)
●の個数 = ○の個数 (図では 10)
Γの個数 = γの個数 (図では 7) (これを $c$ とおきます)
Δの個数 = δの個数 (図では 8) (これを $d$ とおきます)
Εの個数 = εの個数 (図では 5) (これを $e$ とおきます)

となります。
ガウスの補題より

Α(α)の個数が偶数 ⇔ $q$ は $p$ を法とする平方剰余
Β(β)の個数が偶数 ⇔ $p$ は $q$ を法とする平方剰余

よって $\left(\cfrac{q}{p}\right) = (-1)^a$ 、 $\left(\cfrac{p}{q}\right) = (-1)^b$
となります。
[1]の図の右上の部分より
Γ(γ)の個数( $c$ ) + δ(Δ)の個数( $d$ ) = $\cfrac{(p-1)(q-1)}{4}$ (図では 15)
となります。
[2]

0000	×	●	●	●	Δ	Δ	Ε	Α	Γ	Γ	Γ
0001	Β	Δ	Δ	■	●	●	Γ	Ε	Ε	Ε	Α
0002	▲	●	●	Δ	Δ	Δ	Α	Γ	Γ	Γ	Ε
0003	Β	Δ	■	●	●	●	○	○	○	□	δ
0004	β	ε	γ	γ	γ	α	δ	δ	δ	○	○
0005	△	α	ε	ε	ε	γ	○	○	□	δ	δ
0006	β	γ	γ	γ	α	ε	δ	δ	○	○	○

[2]の図の右上の部分より
Α(α)の個数( $a$ ) + Γ(γ)の個数( $c$ ) + Ε(ε)の個数( $e$ ) = $\cfrac{(p-1)(q-1)}{4}$ (図では 15)
となります。
[3]

0000	×	Α	■	Α	Α	■	□	α	α	□	α
0001	●	Γ	●	▲	Γ	●	δ	δ	ε	δ	ε
0002	●	Γ	●	●	Γ	●	β	δ	ε	δ	δ
0003	●	Γ	Γ	●	Γ	●	ε	δ	ε	β	δ
0004	Δ	Β	Ε	Δ	Ε	○	γ	○	γ	γ	○
0005	Δ	Δ	Ε	Δ	Β	○	γ	○	○	γ	○
0006	Ε	Δ	Ε	Δ	Δ	○	γ	△	○	γ	○

[3]の図の右上の部分より
Β(β)の個数( $b$ ) + Δ(δ)の個数( $d$ ) + Ε(ε)の個数( $e$ ) = $\cfrac{(p-1)(q-1)}{4}$ (図では 15)
となります。
よってγの個数を $c$ 、δの個数を $d$ 、εの個数を $e$ とすると
$\begin{eqnarray*} a + b & = & (a + c + e) + (b + d + e) - (c + d) - 2e \\ & = & \cfrac{(p-1)(q-1)}{4} - 2e \end{eqnarray*}$
$\left(\cfrac{q}{p}\right) \left(\cfrac{p}{q}\right) = (-1)^{a+b} = (-1)^{ \frac{(p-1)(q-1)}{4} }$
となります。
[証明終わり]