ルジャンドル記号とオイラーの基準(判定条件)

ルジャンドル記号

 平方剰余/平方非剰余であることを示す ルジャンドル記号 を次のように定めます。

 [定義 F3 ルジャンドル記号] $p$ を奇素数、$(a,\:p)=1$ とするとき

  $\displaystyle\left(\frac{a}{p}\right)=1$ ($a$ が平方剰余のとき)

  $\displaystyle\left(\frac{a}{p}\right)=-1$ ($a$ が平方非剰余のとき)

 法 $11$ の平方剰余は $1,\;3,\;4,\;5,\;9$ , 平方非剰余は $2,\;6,\;7,\;8,\;10$ でしたから、
 
\[\begin{align*}&\left(\frac{1}{11}\right)=\left(\frac{3}{11}\right)=\left(\frac{4}{11}\right)=\left(\frac{5}{11}\right)=\left(\frac{9}{11}\right)=1\\[6pt]
&\left(\frac{2}{11}\right)=\left(\frac{6}{11}\right)=\left(\frac{7}{11}\right)=\left(\frac{8}{11}\right)=\left(\frac{10}{11}\right)=-1\end{align*}\]
のように表すことができます。ほとんど自明のことですが、合同な数 $a$ と $b$ について以下の定理が成り立ちます。

[定理 F10] $p$ を奇素数、$(a,\:p)=1$ とすると、
\[a\equiv b\;(\mathrm{mod}\:p)\quad\Longrightarrow\quad\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)\]

[定理 F10 の証明] $a$ が平方剰余であれば、$b$ も平方剰余なので、
 
\[\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)=1\]
となります。また、$a$ が平方非剰余であれば、$b$ も平方非剰余なので、
 
\[\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)=-1\]
となります。(証明終)
 

オイラーの基準(オイラーの判定条件)

 定理 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)\]

であったので、以下の定理が成り立ちます。

[定理 F9 オイラーの判定条件]
 $p$ を奇素数、$(a,\:p)=(b,\:p)=1$ とするとき、
\[\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\quad (\mathrm{mod}\:p)\]

 この定理を オイラーの基準 もしくは オイラーの判定条件 (Euler's criterion) とよびます。
 

平方剰余の積

 前回記事の 定理 8 を再掲します。

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

 この定理をルジャンドル記号を用いて書き直しておきます。

[定理 F11] $p$ を奇素数、$(a,\:p)=(b,\:p)=1$ とするとき、
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\,\left(\frac{b}{p}\right)\]

[定理 F11 の証明]
(1) $a,\;b$ がともに平方剰余であるとき、すなわち
 
\[\left(\frac{a}{p}\right)=1,\quad\left(\frac{b}{p}\right)=1\]
と表せるとき、定理 F8 より $a\,b$ も平方剰余なので、
 
\[\left(\frac{ab}{p}\right)=1\]
となります。したがって、
 
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\,\left(\frac{b}{p}\right)\]
が成り立っています。
 
(2) $a,\;b$ がともに平方非剰余であるとき、すなわち
 
\[\left(\frac{a}{p}\right)=-1,\quad\left(\frac{b}{p}\right)=-1\]
と表せるときは、定理 F8 より $a\,b$ も平方剰余なので、
 
\[\left(\frac{ab}{p}\right)=1\]
となります。したがって
 
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\,\left(\frac{b}{p}\right)\]
が成り立っています。

(3) $a$ を平方剰余、$b$ を平方非剰余とすると
 
\[\left(\frac{a}{p}\right)=1,\quad\left(\frac{b}{p}\right)=-1\]
と表せます。定理 F8 より $a\,b$ は平方非剰余なので、
 
\[\left(\frac{ab}{p}\right)=-1\]
となります。このときも
 
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\,\left(\frac{b}{p}\right)\]
が成り立っています。$a$ を平方非剰余、$b$ を平方剰余としても同じです。以上 (1), (2), (3) より、定理 F11 が成り立つことが示されました。(証明終)

 ≫ ガウスの補題 ≫ 整数論入門講座

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

コメントをどうぞ

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

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