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

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

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

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

ルジャンドル記号

aapp の平方剰余であるとき,

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

また,aapp の平方剰余でないとき,

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

322(mod7)3^2\equiv 2\pmod{7} より (27)=1\left(\dfrac{2}{7}\right)=1

33 で割って 22 余る平方数は存在しないので (23)=1\left(\dfrac{2}{3}\right)= -1

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

オイラーの規準と具体例

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

オイラーの規準

pp を奇素数,aapp と互いに素な 00 でない整数とするとき

(ap)ap12(modp)\left(\dfrac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}

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

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

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

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

オイラーの規準の証明

必要となる知識はフェルマーの小定理と原始根の存在定理です。

以下 modp\mathrm{mod}\:p の表記を省略します。

証明

(ap)=1\left(\dfrac{a}{p}\right)=1 のとき

ルジャンドル記号の定義より,n2an^2\equiv a となる自然数 nn が存在する。

このとき,aapp は互いに素なので nnpp も互いに素である。

よってフェルマーの小定理より ap12np11a^{\frac{p-1}{2}}\equiv n^{p-1}\equiv 1

・逆に ap121a^{\frac{p-1}{2}}\equiv 1 のとき

pp に対する原始根を rr とおくと,arka\equiv r^k となる自然数 kk が存在する。このとき rk2(p1)1r^{\frac{k}{2}(p-1)}\equiv 1

k2(p1)\dfrac{k}{2}(p-1)p1p-1 の倍数なので(→注)kk は偶数であり,ark=(rk2)2a\equiv r^k=(r^\frac{k}{2})^{2}

となり aapp の平方剰余であることが分かる。

注:rr の位数が p1p-1 であることが分かります,きちんと証明すると以下の通り:

mmp1p-1 で割った商を AA 余りを BB とおくと,

rm=rA(p1)rBrBr^m=r^{A(p-1)}r^B\equiv r^B

より rm1r^m\equiv 1 なら rB1r^B\equiv 1 である。ここで 0<Bp20 <B \leq p-2 だと原始根の定義に矛盾するので B=0B=0 となり mmp1p-1 の倍数。

平方剰余の第一補充法則

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

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

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

これより,奇素数 pp に対して,

pp44 で割って 11 余る素数 ⇔ 1-1pp の平方剰余

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

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

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