平方剰余であるための必要十分条件

平方剰余であるための必要十分条件

 定理 F5 を再掲します。

[定理 F5] $d=(n,\:p-1)$ とおくと
      $x^n\equiv a\;(\mathrm{mod}\:p)$ が解をもつ $\Longleftrightarrow\quad a^{\frac{p-1}{d}}\equiv 1\quad (\mathrm{mod}\:p)$

 この定理において $p$ を奇素数、$n=2$ とすると、$p-1$ は偶数なので
 
\[d=(n,\:p-1)=(2,\:p-1)=2\]
となり、次の定理が得られます。

[定理 F6] $p$ を奇素数、$p\mid \hspace{-.67em}/\,a$ とすると、
     $a$ が平方剰余であるための必要十分条件は
\[a^{\frac{p-1}{2}}\equiv 1\quad (\mathrm{mod}\:p)\]

 平方非剰余であるための必要十分条件も調べておきます。
 フェルマーの小定理 $a^{p-1}\equiv 1\;(\mathrm{mod}\:p)$ より、
 
\[\left(a^{\frac{p-1}{2}}-1\right)\,\left(a^{\frac{p-1}{2}}+1\right)\equiv 0\quad (\mathrm{mod}\:p)\]
 平方非剰余なので、
 
\[a^{\frac{p-1}{2}}\not\equiv 1\quad (\mathrm{mod}\:p)\]
 したがって次の定理が成り立ちます。

[定理 F7] $p$ を奇素数、$p\mid \hspace{-.67em}/\,a$ とすると、
     $a$ が平方非剰余であるための必要十分条件は
\[a^{\frac{p-1}{2}}\equiv -1\quad (\mathrm{mod}\:p)\]

 定理 F6 と F7 によると $a^{\frac{p-1}{2}}$ は $1$ か $-1$ のどちらかの値しかとりません。
 $1$ であれば平方剰余、$-1$ でれば平方非剰余となります。
 法 $11$ で確認してみます。$(p-1)/2=5$ なので
 
\[\begin{align*}&1^5\equiv 1\quad (\mathrm{mod}\:11)\\[6pt]
&2^5=32\equiv -1\quad (\mathrm{mod}\:11)\\[6pt]
&3^5=243\equiv 1\quad (\mathrm{mod}\:11)\\[6pt]
&4^5=(2^5)^2= (2^5)^2=(-1)^2\equiv 1\quad (\mathrm{mod}\:11)\\[6pt]
&5^5=25\times 125=3\times 4=12\equiv 1\quad (\mathrm{mod}\:11)\\[6pt]
&6^5=6\times 36\times 36\equiv -5\times 3\times 3=-45\equiv -1\quad (\mathrm{mod}\:11)\\[6pt]
&7^5=7\times 49\times 49\equiv -4\times 5\times 5=-100\equiv -1\quad (\mathrm{mod}\:11)\\[6pt]
&8^5=8\times 64\times 64\equiv -3\times 9\times 9\equiv -3\times 4\equiv -1\quad (\mathrm{mod}\:11)\\[6pt]
&9^5=(3^2)^5=(3^5)^2=1^2\equiv 1\quad (\mathrm{mod}\:11)\\[6pt]
&10^5=10\times 10\times 100\equiv -1\times 1\times 1\equiv -1\quad (\mathrm{mod}\:11)\end{align*}\]
 したがって、法 $11$ の平方剰余は $1,\;3,\;4,\;5,\;9$ であり、その他は平方非剰余となります。 ≫ 平方剰余同士の積 ≫ 整数論入門講座

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

コメントをどうぞ

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

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