ガウスの補題

ガウスの補題

 たとえば、$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\]が成り立ちます。

[定理 F12 の証明] $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\]
が成り立ちます。(証明終) ≫ 整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください