2.5.1 ルジャンドルの記号

$p$を素数とし、$a$を$p$と素な整数とします。このとき2次方程式

$$x^2\equiv a \pmod{p}$$

の解の有無について考えてみましょう。$a$を$p$と素な整数に限定するのは、$a$が$p$の倍数のとき $a\equiv 0 \pmod{p}$であり解があることが自明であるためです。

素数を法とする合同類には原始根があり、すべての合同類は原始根のべき乗で表すことができます。したがって、$r$を原始根とすると任意の合同類は、 $r^d,(d=0,1,\cdots,p-1)$で表すことができます。 $\overline{a} \mod{p}$が属する剰余類が$r^d$と表されるとき、$d$が偶数の場合、 $x=r^{\frac{d}{2}}$とすると、 $x^2= r^d= a \mod{p}$となるため、上の式が解を持つことが分かります。

逆に上の式が解をもつと仮定すると、$x=r^d$とおけ、 $x^2=r^{2d}\equiv a \pmod{p}$となるため、$a$は原始根の偶数乗であることが分かります。

つまり、上の2次合同式の$a$が原始根の偶数乗のとき、上の合同式は解を持ち、逆に、解を持つときは$a$が原始根の偶数乗のときに限ります。

この考察は原始根$r$の取り方に依存していないことに注意しましょう。このことは、下記の補題からも確認できます。

補題 2.5.1
$p$を素数とし、$r_1,r_2$を$p$を法とする2つの原始根とする。 （定理2.4.26より、原始根は$\phi(p-1)$個存在します。）
$p$を法とする1つの合同類$a$を、$r_1$及び$r_2$のべき乗で表したとき、その偶奇は一致する。つまり、 $a=r_1^n=r_2^m$のときの$n$と$m$の偶奇は等しい。

証明
$p$を法とする合同類$a$が $a=r_1^n=r_2^m$と表されたとき、$n,m$の偶奇が一致することを示す。
$r_1$は原始根であるため、$r_2=r_1^a$と表すことができ、このとき$r_2$が原始根であることより、$a$は$p-1$と互いに素となる（命題3.1.14参照）。$p=2$のとき成り立つのは明らかであるため、$p$は奇素数と仮定してよい。すると、$p-1$は偶数となるため$a$は奇数である。
$r_2^m=r_1^{am}=r_1^{n}$であり、$p-1\vert am-n$であるが、$p-1$が偶数であり$a$が奇数であるため$n,m$の偶奇は一致する。

定義 2.5.2
$p$を素数とするとき2次合同式

$$x^2\equiv a \pmod{p}$$

が解をもつような$a$のことを$p$を法として平方剰余（quadratic residue）といい解がをもたないような$a$のことを$p$を法として平方非剰余（quadratic nonresidue）という。

ここで、ルジャンドル記号 $a\overwithdelims () p$を次のように導入します。

$${a\overwithdelims () p} = \begin{cases} 1 & aがpを法として平方剰余\\ -1 & aがpを法として平方非剰余\\ \end{cases}$$

フェルマーの小定理より、0以外の合同類は$p-1$乗すると $\overline{1}$になりますが、合同類が原始根の偶数乗と表されるときは $\frac{p-1}{2}$乗することにより $\overline{1}$となり、原始根の奇数乗と表されるときは $\frac{p-1}{2}$乗すると $\overline{-1}$となることが分かります。したがって、ルジャンドル記号は、 $\frac{p-1}{2}$乗と等しいことがわかります 以上のルジャンドル記号の性質をまとめると次のようになります。

命題 2.5.3
$p$を素数$a$を$p$と素な整数とすると、

$$x^2\equiv a \pmod{p}が解を持つ \Longleftrightarrow {a\overwithdelims () p}=1$$

$$\Longleftrightarrow aが\mod{p}で原始根の偶数乗となる$$

$$\Longleftrightarrow a^{\frac{p-1}{2}}\equiv 1 \pmod{p}$$

$$x^2\equiv a \pmod{p}が解を持たない \Longleftrightarrow {a\overwithdelims () p}=-1$$

$$\Longleftrightarrow aが\mod{p}で原始根の奇数乗となる$$

$$\Longleftrightarrow a^{\frac{p-1}{2}}\equiv -1 \pmod{p}$$

ルジャンドル記号の基本的な性質をみていきましょう。$2$以外の素数は奇数ですので$2$でない素数を奇素数（odd prime）といいます。

定理 2.5.4 (ルジャンドル記号の性質)
$p$を奇素数、$a,b$を$p$と素な整数とすると、
（1） ${a\overwithdelims () p}\equiv a^{\frac{p-1}{2}} \pmod{p}$
（2） ${ab\overwithdelims () p}={a\overwithdelims () p}{b\overwithdelims () p}$
（3） (第一補充法則) ${-1\overwithdelims () p}=(-1)^{\frac{p-1}{2}}$
（4） (第二補充法則) ${2\overwithdelims () p}=(-1)^{\frac{p^2-1}{8}}$

証明
（1）（3）は、上の命題から明らか。
（2）は（1）より明らか。
（4）は次節で平方剰余の相互法則と一緒に証明します。

（2）は、 ${\cdot \overwithdelims () p}$が $(\mathbb{Z}/p\mathbb{Z})^\times$から $\{\pm 1\}\subset\mathbb{C}^\times$への群準同型写像であることを意味しています。つまり、

$$\begin{array}{rccc} {\cdot \overwithdelims () p}:&(\mathbb{... ...ngmapsto & {a \overwithdelims () p} \ \end{array}$$

は準同型写像です。群$G$から $\mathbb{C}^\times$の群準同型写像を指標（character）といいます。ルジャンドル指標は、 $(\mathbb{Z}/p\mathbb{Z})^\times$の指標と考えることができます。

また、（4）の意味するところは以下のとおりです。 2でない素数$p$は、$\mod{8}$で、1,3,5,7のいずれかです。そして、1,7のとき、 $\dfrac{p^2-1}{8}$が偶数となり、3,5のとき奇数になりますしたがって（4）を言い換えると次のようになります。

命題 2.5.5 (第2補充法則)
$p$を奇素数とすると

$$p\equiv 1,7 \mod{8} \Longleftrightarrow {2\overwithdelims () p}=(-1)^{\frac{p^2-1}{8}}=1$$

$$p\equiv 3,5 \mod{8} \Longleftrightarrow {2\overwithdelims () p}=(-1)^{\frac{p^2-1}{8}}=-1$$