平方剰余と平方非剰余

平方剰余と平方非剰余

 完全平方数
 
\[1,\;4,\;9,\;16,\;25,\;36,\;49,\;64,\;81,\;\cdots\]
を 3 で割った余りを並べてみると ......
 
\[1,\;1,\;0,\;1,\;1,\;0,\;1,\;1,\;0,\;\cdots\]
というように $1,\;1,\;0$ が周期的に並びます。つまり、どのような平方数も $3$ で割ったときの余りは $0$ か $1$ のどちらかであるということです。上の例については
 
\[n=3k-2,\quad 3k-1,\quad 3k\quad (k=1,\;2,\;\cdots)\]
をそれぞれ平方してみれば
 
\[9k^2-12k+4,\quad 9k^2-6k+1,\quad 9k^2\]
となるので、$3$ で割ると余りが
 
\[1,\;1,\;0,\;1,\;1,\;0,\;1,\;1,\;0,\;\cdots\]
というように交互に並ぶことがわかります。以上の事実は合同方程式
 
\[x^2\equiv a\quad (\mathrm{mod}\:3)\]
は $a$ が $1$ または $0$ のときに限って解をもつということを示していて、
 
\[x^2\equiv 2\quad (\mathrm{mod}\:3)\]
には解がない(余りが $2$ となることはない)ということです。平方数を素数で割ったときの余りを表にしてみると次のようになります。

 エクセルで作成した平方剰余表

 表を眺めてみると、たとえば平方数を $7$ で割ったときの余りは $0$ を除けば $1,\;2,\;4$ に限られていることがわかります。以上の事実を踏まえて、平方剰余平方非剰余 を次のように定義します。

[定義 F2] 素数 $p$ を法とするr 2 項合同方程式
\[x^2\equiv a\quad (\mathrm{mod}\:p)\]が整数解を $x$ をもつときの正整数 $a$ を法 $p$ の平方剰余 (quadratic residue) といい、解をもたないときの $a$ を法 $p$ の平方非剰余 (quadratic non-residue) といいます。

 $a$ を正整数と定義しているので、$0$ は平方剰余の定義から外します。たとえば $\mathrm{mod}\:3$ の平方剰余は $a=1$ であり、平方非剰余は $a=2$ ということになります。また、$\mathrm{mod}\:7$ の平方剰余は $a=1,\;2,\;4$ であり、平方非剰余は $a=3,\;5,\;6$ となります。$1^2\equiv 1\quad (\mathrm{mod}\:p)$ なので、$1$ は法の選択に関わらず常に平方剰余です。また、
 
\[x^2\equiv (p-x)^2\quad (\mathrm{mod}\:p)\]
が成り立つので、平方剰余の個数は $(p-1)/2$ 個であり、たとえば $p=7$ の場合は $(p-1)/2=3$ なので、$1$ から $3$ まで平方して
 
\[\begin{align*}1^2\equiv 1\quad (\mathrm{mod}\:7)\\[6pt]
2^2\equiv 4\quad (\mathrm{mod}\:7)\\[6pt]
3^2\equiv 2\quad (\mathrm{mod}\:7)\end{align*}\]
 これですべての平方剰余が出揃ったことになります。上の表でも各法で $x=(p-1)/2$ のところで平方剰余が揃うことを確認しておいてください。次回以降の記事では様々な定理を使って、この平方剰余/平方非剰余について詳しく調べていきます。

 ≫ 平方剰余であるための必要十分条件 ≫ 整数論入門講座

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

コメントをどうぞ

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

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