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

ルジャンドル記号

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

法 $11$ の平方剰余は $1,3,4,5,9$ , 平方非剰余は $2,6,7,8,10$ でしたから、
$$\begin{array}{rl}& \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\\ & \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{array}$$
のように表すことができます。ほとんど自明のことですが、合同な数 $a$ と $b$ について以下の定理が成り立ちます。

[証明] $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 を再掲します：

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

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

平方剰余の積

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

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

[証明]
(1) $a,b$ がともに平方剰余であるとき、すなわち
$$\left(\frac{a}{p}\right)=1,\left(\frac{b}{p}\right)=1$$
と表せるとき、定理 F8 より $ab$ も平方剰余なので、
$$\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,\left(\frac{b}{p}\right)=-1$$
と表せるときは、定理 F8 より $ab$ も平方剰余なので、
$$\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,\left(\frac{b}{p}\right)=-1$$
と表せます。定理 F8 より $ab$ は平方非剰余なので、
$$\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 が成り立つことが示されました。（証明終）

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