平方剰余同士の積は平方剰余です

平方剰余の乗算表

 前回記事 で法 $11$ の平方剰余は $1,\;3,\;4,\;5,\;9$ , 平方非剰余は $2,\;6,\;7,\;8,\;10$ であることを調べました。そこで今回は平方剰余同士、平方非剰余同士、あるいは平方剰余と平方非剰余の積がどのようになるのかを乗算表をつくって調べてみます。まず最初に「平方剰余 × 平方剰余」を $11$ で割った余りを表に並べてみます。

 エクセル平方剰余×平方剰余

 見ての通り、平方剰余同士の積をつくると $1,\;3,\;4,\;5,\;9$ だけが並びます。すなわち

平方剰余 × 平方剰余 = 平方剰余

となっています。次は平方非剰余同士の積です。

 エクセル平方非剰余×平方非剰余

 この場合も $1,\;3,\;4,\;5,\;9$ だけが並びます。すなわち

平方非剰余 × 平方非剰余 = 平方剰余

です。最後に平方剰余と平方非剰余の積を調べてみます。

 Excel 平方剰余×平方非剰余

 今度は $2,\;6,\;7,\;8,\;10$ だけが並んでいます。すなわち

平方剰余 × 平方非剰余 = 平方非剰余

となっています。
 

平方剰余同士の積は平方剰余です

 一般に以下の定理が成り立ちます。

[定理 F8] $p$ を奇素数、$(a,\:p)=(b,\:p)=1$ とするとき、
(1) $a,\;b$ がともに $p$ の平方剰余であれば、$ab$ は平方剰余
(2) $a,\;b$ がともに $p$ の平方非剰余であれば、$ab$ は平方剰余
(3) $a,\;b$ のうち一方が平方剰余、他方が平方非剰余であれば、$ab$ は平方非剰余

[定理 F8 の証明] 前回記事の定理 F6 と F7 を用います:

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

(1) $a,\;b$ がともに平方剰余なので
 
\[(ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}\,b^{\frac{p-1}{2}}\equiv 1\cdot 1=1\quad (\mathrm{mod}\:p)\]
 したがって、$ab$ は平方剰余です。

(2) $a,\;b$ がともに平方非剰余なので
 
\[(ab)^{\frac{p-1}{2}}\equiv (-1)\cdot (-1)=1\quad (\mathrm{mod}\:p)\]
 したがって、$ab$ は平方剰余です。

(3) $a,\;b$ のうち一方が平方剰余、他方が平方非剰余なので
 
\[(ab)^{\frac{p-1}{2}}\equiv 1\cdot (-1)=-1\quad (\mathrm{mod}\:p)\]
 よって、$ab$ は平方非剰余となります。(証明終)

 ≫ ルジャンドル記号とオイラーの基準 ≫ 整数論入門講座

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

コメントをどうぞ

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

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