ガウスの補題についてのメモ(1): 補題の証明

平方剰余についてのガウスの補題は次のようなもの。

$a$ は $p$ で割り切れない数とし、 $\left(\frac{a}{p}\right)$ はルジャンドル記号とする。
$a,2a,3a,\ldots,\frac{p-1}{2}a$ を素数 $p$ で割った余りのうち $\frac{n}{2}$ より大きいものの個数を $l$ 個とすると

$\left(\frac{a}{p}\right) = (-1)^l$

これをどうやって証明するか以前に、どうして唐突に「 $\frac{n}{2}$ より大きいものの個数」なんてものが出てきたのかという疑問が浮かぶ。

これはフェルマーの小定理の乗法的証明と比較するといくらか理解しやすい。

フェルマーの小定理 $a^{p-1} \equiv 1 \; \pmod p$ の証明:
$1,2,3,\ldots,p-1$ のそれぞれに $a$ をかけて $p$ で割った余り

$a,2a,3a,\ldots,(p-1)a \;\pmod p$

を考えると、これらは全て異なっている。

全て異なることの説明:
ユークリッドの互除法を用いると $ax+py=1$ となる $x$ が求まり、この $x$ は $ax \equiv 1 \pmod p$ を満たす。つまり ${}\bmod p$ の世界では、 $x$ は $a$ の逆数になる。よって

$a,2a,3a,\ldots,(p-1)a \;\pmod p$

のそれぞれに $x$ をかけると

$1,2,3,\ldots,p-1 \;\pmod p$

となる。明らかにこれらは全て異なる値になる。なので、もしも

$a,2a,3a,\ldots,(p-1)a \;\pmod p$

の中に等しいものがあったとすると、それぞれに $x$ をかけた

$1,2,3,\ldots,p-1 \;\pmod p$

の中にも等しいものがあることになって矛盾してしまう。よって

$a,2a,3a,\ldots,(p-1)a \;\pmod p$

は全て異なる。

したがって

$\left\{ 1,2,3,\ldots,p-1 \right\} \; \pmod p$

と

$\left\{ a,2a,3a,\ldots,(p-1)a \right\} \;\pmod p$

は要素が一致しているので、それぞれの要素を全てかけあわせれば

$(p-1)! \equiv a^{p-1} (p-1)! \; \pmod p$

となる。
ユークリッドの互除法から

$x (p-1)! \equiv 1 \pmod p$

となる $x$ の存在が言えるので、この $x$ を両辺にかければ

$1 \equiv a^{p-1} \; \pmod p$

となる。(証明終わり)

この証明を参考にガウスの補題を証明する。
まずルジャンドル記号には「オイラーの基準」と呼ばれる次の性質がある。

$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \; \pmod p$

これとフェルマーの小定理

$1 \equiv a^{p-1} \; \pmod p$

の形の類似を見ると、フェルマーの小定理の証明と似た議論をすると何か得られるのではという見込みが立つ。

ガウスの補題の証明:

$\left\{ 1,2,3,\ldots,\frac{p-1}{2} \right\}$

のそれぞれに $a$ をかけて $p$ で割った余りをとると

$\left\{a,2a,3a,\ldots,\frac{p-1}{2}a\right\}\pmod p$

という集合が得られる。ここで、これらの要素の値は全て異なっている。
これらの要素の中に $p/2$ より大きいものがあるとすると、もとの集合

$\left\{1,2,3,\ldots,\frac{p-1}{2}\right\}$

とは一致しない。なぜなら $\left\{1,2,3,\ldots,(p-1)/2\right\}$ の各要素は全て $p/2$ より小さいので。
そこで

$\left\{a,2a,3a,\ldots,\frac{p-1}{2}a\right\}\; \pmod p$

のなかに $p/2$ より大きいものがあればその

$ka \;\pmod p$

を取り除いて

$-ka \; \pmod p$

に置き換えることにする。このとき、 $0 < -ka \; \pmod p < p/2$ 、となる。
ここで $\epsilon(k)$ という記号を導入して、 $ka \pmod p$ が $p/2$ より大きいときは $\epsilon(k)=-1$ 、そうでないときは $\epsilon(k)=1$ となる $\epsilon(k)$ を表すことにすれば、置き換えの結果

$\left\{\epsilon(1) a,\epsilon(2) 2a,\epsilon(3) 3a,\ldots,\epsilon(\frac{p-1}{2}) \frac{p-1}{2}a\right\}\pmod p$