オイラーの基準（判定条件）

ルジャンドル記号
オイラーの基準（オイラーの判定条件）
平方剰余の積

ルジャンドル記号

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

【定義F3：ルジャンドル記号】$p$ を奇素数、$(a,\:p)=1$ とするとき
$\qquad\displaystyle\left(\frac{a}{p}\right)=1$　($a$ が平方剰余のとき）
$\qquad\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)\]

[証明] $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)\]

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

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