当サイトではアフィリエイトプログラムを利用して商品を紹介しています。

ガウスの補題

ガウスの補題

たとえば、$p=11,\;a=5$ として、
$a$ の $1$ から $(p-1)/2=5$ 倍までの倍数をつくると、
\[1\cdot 5,\quad 2\cdot 5,\quad 3\cdot 5,\quad 4\cdot 5,\quad 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=\left(\frac{5}{11}\right)=1\]
という関係が成り立っています。このことを一般的に述べたのがガウスの補題です。

【定理F12:ガウスの補題】
$p$ を奇素数、$r=(p-1)/2,\;(a,\:p)=1$ として、
$a$ の $r$ 倍までの倍数をつくる。
\[1\cdot a,\quad 2\cdot a,\quad 3\cdot a,\quad 4\cdot a,\quad 5\cdot a\]これらの法 $p$ による絶対最小値剰余を
\[a_1,\;a_2,\;a_3,\;\cdots,\;a_r\]とし、負の項数を $t$ とすれば
\[\left(\frac{a}{p}\right)=(-1)^t\]が成り立つ。

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

\[a_1,\;a_2,\;a_3,\;\cdots,\;a_r\tag{a}\]
はすべて $\mathrm{mod}\:p$ で異なります。実際、仮に
\[ai\equiv ak\;(\mathrm{mod}\:p)\quad 1\leq i,\:k\leq r\]
が成り立っているとすると、
\[a(i-k)\equiv 0\quad (\mathrm{mod}\:p)\]
$(a,\:p)=1$ より、$i=k$ となります。また仮に
\[ai\equiv (-ak)\;(\mathrm{mod}\:p)\quad 1\leq i,\:k\leq r\]
が成り立っているならば、
\[a(i+k)\equiv 0\quad (\mathrm{mod}\:p)\]
$(a,\:p)=1$ より、$i\equiv k$ とならなければなりませんが、
\[1\leq i,\:k\leq\frac{p-1}{2}\]
より、$i+k\leq p-1\lt p$ なので不可能です。よって、(1) は符号を無視すれば $1,\;2,\;3,\;\cdots,\;r$ がすべて現れることになります。また (1) の負の項の個数を $t$ とすると、
\[a_1\,a_2\,a_3\,\cdots\,a_r=(-1)^t\,r!\]
となります。また $a$ の倍数について積をつくると
\[(1a)\,(2a)\,(3a)\,\cdots\,(ra)=a^r\,r!\]
となるので、
\[a^r\,r!\equiv (-1)^t\,r!\quad (\mathrm{mod}\:p)\]
が成り立ちます。$(r!,\:p)=1$ なので
\[a^{\frac{p-1}{2}}\equiv (-1)^t\quad (\mathrm{mod}\:p)\]
前回記事で扱ったオイラーの判定条件
\[\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\quad (\mathrm{mod}\:p)\]
を用いると、
\[\left(\frac{a}{p}\right)=(-1)^t\]
が成り立ちます。(証明終)

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