ガウスの補題

ガウスの補題

たとえば、$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\]
という関係が成り立っています。このことを一般的に述べたのがガウスの補題です。

[証明] $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\]
が成り立ちます。（証明終）