ガウスの補題

たとえば、 $p = 11, a = 5$ として、
$a$ の $1$ から $(p - 1) / 2 = 5$ 倍までの倍数をつくると、
$1 \cdot 5, 2 \cdot 5, 3 \cdot 5, 4 \cdot 5, 5 \cdot 5$
これらを $p = 11$ で割った余りを並べると
$5, 10, 4, 9, 3$
さらに $11 / 2 = 5.5$ よりも大きな数については、 $11$ を引いて絶対最小値剰余にします。
$5, - 1, 4, - 2, 3$
符号を無視すると、 $1$ から $5$ までの数字が全て現れています。
また、負の項は 2 つで、前回記事のルジャンドル記号を用いると
$(- 1)^{2} = (\frac{5}{11}) = 1$
という関係が成り立っています。このことを一般的に述べたのがガウスの補題です。

【定理F12：ガウスの補題】

p

を奇素数、

r = (p - 1) / 2, (a, p) = 1

として、

a

の

r

倍までの倍数をつくる。

1 \cdot a, 2 \cdot a, 3 \cdot a, 4 \cdot a, 5 \cdot a

これらの法

p

による絶対最小値剰余を

a_{1}, a_{2}, a_{3}, \dots, a_{r}

とし、負の項数を

t

とすれば

(\frac{a}{p}) = (- 1)^{t}

が成り立つ。

[証明] $a$ の $r$ 倍までの倍数
$1 \cdot a, 2 \cdot a, 3 \cdot a, 4 \cdot a, 5 \cdot a$
の絶対最小値剰余

$\begin{matrix} (a) & a_{1}, a_{2}, a_{3}, \dots, a_{r} \end{matrix}$
はすべて $\mod p$ で異なります。実際、仮に
$a i \equiv a k (\mod p) 1 \leq i, k \leq r$
が成り立っているとすると、
$a (i - k) \equiv 0 (\mod p)$
$(a, p) = 1$ より、 $i = k$ となります。また仮に
$a i \equiv (- a k) (\mod p) 1 \leq i, k \leq r$
が成り立っているならば、
$a (i + k) \equiv 0 (\mod p)$
$(a, p) = 1$ より、 $i \equiv k$ とならなければなりませんが、
$1 \leq i, k \leq \frac{p - 1}{2}$
より、 $i + k \leq p - 1 < p$ なので不可能です。よって、(1) は符号を無視すれば $1, 2, 3, \dots, r$ がすべて現れることになります。また (1) の負の項の個数を $t$ とすると、
$a_{1} a_{2} a_{3} \dots a_{r} = (- 1)^{t} r!$
となります。また $a$ の倍数について積をつくると
$(1 a) (2 a) (3 a) \dots (r a) = a^{r} r!$
となるので、
$a^{r} r! \equiv (- 1)^{t} r! (\mod p)$
が成り立ちます。 $(r!, p) = 1$ なので
$a^{\frac{p - 1}{2}} \equiv (- 1)^{t} (\mod p)$
前回記事で扱ったオイラーの判定条件
$(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} (\mod p)$
を用いると、
$(\frac{a}{p}) = (- 1)^{t}$
が成り立ちます。（証明終）

ガウスの補題

エクセルや数学に関するコメントをお寄せください