2014/09/01

ルジャンドル記号とオイラーの規準

分野: 整数問題  レベル: 数学オリンピック

$n^2\equiv a\:\mathrm{mod}\:p$ となる整数 $a$ が存在するとき $a$ を $p$ の平方剰余と言います。平方剰余の基本的な話題は平方剰余と基本的な問題を参照して下さい。このページでは平方剰余に関するより発展的な話題を扱います。

ルジャンドル記号と具体例

$a$ が $p$ の平方剰余か否かを簡潔に表すためにルジャンドル記号$(\dfrac{a}{p})$ というものが用いられています。

$a$ が $p$ の平方剰余であるとき,
$\left(\dfrac{a}{p}\right)=1$ と定義します。
また,$a$ が $p$ の平方剰余でないとき,
$\left(\dfrac{a}{p}\right)=-1$ と定義します。

数学的に新しいことは何もありませんが,ルジャンドル記号を導入することで様々な議論,定理を簡潔に表現することができるので広く用いられます。

$3^2\equiv 2\:\mathrm{mod}\:7$ より $\left(\dfrac{2}{7}\right)=1$
$3$ で割って $2$ 余る平方数は存在しないので $\left(\dfrac{2}{3}\right)= -1$

オイラーの規準と具体例

平方剰余かどうかを判定するための定理の1つにオイラーの規準と呼ばれるものがあります。

オイラーの規準:
$p$ を奇素数,$a$ を $p$ と互いに素な $0$ でない整数とするとき
$\left(\dfrac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\:\mathrm{mod}\:p$

$\left(\dfrac{2}{7}\right)\equiv 2^3\equiv 1 \:\mathrm{mod}\:7$ より $2$ が $7$ の平方剰余であることが分かる。
$\left(\dfrac{2}{3}\right)\equiv 2^1\equiv -1\:\mathrm{mod}\:3$ より $2$ は $3$ の平方非剰余であることが分かる。

「 $p$ が奇素数,$a$ と $p$ が互いに素」という制約はありますが,オイラーの規準を用いれば平方剰余かどうかを簡単な計算で判定することができます。

オイラーの規準を知らないと解けない問題は出題されませんが,数学オリンピックの整数問題では整数に具体的な値を代入して実験するのが大事であり,その過程でそれなりに大きい $p$ に対して平方剰余か素早く判定できると便利な場合があります。

オイラーの規準の証明

必要となる知識はフェルマーの小定理と原始根の存在定理です。
→フェルマーの小定理の証明と例題
→原始根の定義と具体例
以下 $\:\mathrm{mod}\:p$ の表記を省略します。

証明

・ $\left(\dfrac{a}{p}\right)=1$ のとき
ルジャンドル記号の定義より,$n^2\equiv a$ となる自然数 $n$ が存在する。
このとき,$a$ と $p$ は互いに素なので $n$ と $p$ も互いに素である。
よってフェルマーの小定理より $a^{\frac{p-1}{2}}\equiv n^{p-1}\equiv 1$

・逆に $a^{\frac{p-1}{2}}\equiv 1$ のとき
$p$ に対する $a$ の原始根を $r$ とおくと,$a\equiv r^k$ となる自然数 $k$ が存在する。このとき $r^{\frac{k}{2}(p-1)}\equiv 1$

$\dfrac{k}{2}(p-1)$ は $p-1$ の倍数なので(注)$k$ は偶数であり,$a\equiv r^k=(r^2)^{\frac{k}{2}}$
となり $a$ が $p$ の平方剰余であることが分かる。

注:$r$ の位数が $p-1$ であることが分かります,きちんと証明すると以下の通り:
$m$ を $p-1$ で割った商を $A$ 余りを $B$ とおくと,
$r^m=r^{A(p-1)}r^B\equiv r^B$
より $r^m\equiv 1$ なら $r^B\equiv 1$ である。ここで $0 <B \leq p-2$ だと原始根の定義に矛盾するので $B=0$ となり $m$ は $p-1$ の倍数。

平方剰余の第一補充法則

特によく使うのがオイラーの規準で $a=-1$ とした場合です:
$\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$
これを平方剰余の第一補充法則と言います。
これより,奇素数 $p$ に対して,

$p$ が $4$ で割って $1$ 余る素数⇔$-1$ が $p$ の平方剰余

ということが分かります。

この定理のエレガントな応用例としてフェルマーの二平方和定理が挙げられます。

原始根はいろいろな定理の証明に使えるのでもっと普及すると嬉しいです。
分野: 整数問題  レベル: 数学オリンピック