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

ルジャンドル記号

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

 [定義 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) とよびます。
 

平方剰余の積

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

 [定理 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 が成り立つことが示されました。(証明終)

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

エクセルや数学に関するコメントをお寄せください