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

更新 2021/03/06

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

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

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

ルジャンドル記号

$a$ が $p$ の平方剰余であるとき，

$\left(\dfrac{a}{p}\right)=1$ と定義します。

また， $a$ が $p$ の平方剰余でないとき，

$\left(\dfrac{a}{p}\right)=-1$ と定義します。

例

$3^2\equiv 2\pmod{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}}\pmod{p}$

例

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

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

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

数学オリンピックなどの整数問題では，整数に具体的な値を代入して実験するのが大事であり，その際にそれなりに大きい $p$ に対して平方剰余か素早く判定できると便利な場合があります。

オイラーの規準の証明

必要となる知識はフェルマーの小定理と原始根の存在定理です。
フェルマーの小定理の証明と例題
原始根の定義と具体例
以下 mod p\mathrm{mod}\:pmodp
 の表記を省略します。
証明
・
(ap)=1\left(\dfrac{a}{p}\right)=1(pa​)=1
 のとき
ルジャンドル記号の定義より，n2≡an^2\equiv an2≡a
 となる自然数
nnn
 が存在する。
このとき，aaa
 と
ppp
 は互いに素なので
nnn
 と
ppp
 も互いに素である。
よってフェルマーの小定理より
ap−12≡np−1≡1a^{\frac{p-1}{2}}\equiv n^{p-1}\equiv 1a2p−1​≡np−1≡1
・逆に
ap−12≡1a^{\frac{p-1}{2}}\equiv 1a2p−1​≡1
 のとき
ppp
 に対する原始根を
rrr
 とおくと，a≡rka\equiv r^ka≡rk
 となる自然数
kkk
 が存在する。このとき
rk2(p−1)≡1r^{\frac{k}{2}(p-1)}\equiv 1r2k​(p−1)≡1
k2(p−1)\dfrac{k}{2}(p-1)2k​(p−1)
 は
p−1p-1p−1
 の倍数なので（→注）kkk
 は偶数であり，a≡rk=(rk2)2a\equiv r^k=(r^\frac{k}{2})^{2}a≡rk=(r2k​)2
となり
aaa
 が
ppp
 の平方剰余であることが分かる。
注：rrr
 の位数が
p−1p-1p−1
 であることが分かります，きちんと証明すると以下の通り：
mmm
 を
p−1p-1p−1
 で割った商を
AAA
 余りを
BBB
 とおくと，
rm=rA(p−1)rB≡rBr^m=r^{A(p-1)}r^B\equiv r^Brm=rA(p−1)rB≡rB
より
rm≡1r^m\equiv 1rm≡1
 なら
rB≡1r^B\equiv 1rB≡1
 である。ここで
0<B≤p−20 <B \leq p-20<B≤p−2
 だと原始根の定義に矛盾するので
B=0B=0B=0
 となり
mmm
 は
p−1p-1p−1
 の倍数。

平方剰余の第一補充法則

特によく使うのがオイラーの規準で $a=-1$ とした場合です：

$\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$

これを平方剰余の第一補充法則と言います。

これより，奇素数 $p$ に対して，

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

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

この定理のおもしろい応用例としてフェルマーの二平方和定理があります。

原始根はいろいろな定理の証明に使えるので，もっと有名になると嬉しいです。

この記事の監修者

マスオ

東京大学大学院情報理工学系研究科修了／2014年にWebサイト『高校数学の美しい物語』を立ち上げ／著書累計 50,000部突破／「わかりやすいこと」と「ごまかさないこと」の両立を意識している。 →著者情報・書籍一覧を見る