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

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

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

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

これをどうやって証明するか以前に、どうして唐突に「 $\frac{p}{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$ (つまり (p-1)!の逆元)の存在が言えるので、この $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$

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

ガウスの補題の証明:
以下 $\pmod p$ はだいたい省略して、全てpで割った余りで考える。

集合 $\left\{1,2,3,\ldots,p-1 \right\} = \left\{ 1,2,3,\ldots,\frac{p-1}{2},\frac{p+1}{2},\ldots,p-3,p-2,p-1\right\} \\ = \left\{ 1,2,3,\ldots,\frac{p-1}{2},-\frac{p-1}{2},\ldots,-3,-2,-1\right\}$

を

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

のふたつに分けて、各要素に $a$ をかけると

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

という集合が得られる。これらのn-1個の要素は全て異なっている。
次に

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

の各要素 $ka$ のうち $\frac{p}{2}$ より大きいものがあれば、その要素をもうひとつの集合に含まれている $-ka$ と入れ替える。
ここで $\epsilon(k)$ という記号を導入して、 $ka$ が $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\} \\ \left\{-\epsilon(1) a,-\epsilon(2) 2a,-\epsilon(3) 3a,\ldots,-\epsilon(\frac{p-1}{2}) \frac{p-1}{2}a\right\}$