初等整数論/平方剰余の相互法則の証明のソースを表示

{{Nav}}

平方剰余の相互法則の証明は様々なものが知られているが、初等的な証明として、アイゼンシュタインによる、ガウスの補題の変形と、幾何的な考えを用いた証明が知られている。
まず、ガウスの補題の変形から始める。

== ガウスの補題の変形 ==
''p'', ''q'' が相異なる奇素数のとき
:<math>\left(\frac{q}{p}\right)=(-1)^{\sum_{a=0}^{\frac{p-1}{2}}\left\lfloor\frac{2aq}{p}\right\rfloor}</math>
が成り立つ。つまり
<math>\left(\frac{q}{p}\right)</math> は <math>\left\lfloor\frac{2aq}{p}\right\rfloor (a=0, 1, \ldots, (p-1)/2)</math> が奇数となるものの個数と一致する。

'''証明''' <br />
''aq'' を ''p'' で割った余りが <math>\frac{p}{2}</math> より大きい <math>\iff \left\lfloor\frac{2aq}{p}\right\rfloor</math> が奇数が成り立つことを示せばよい。
実際
:<math>aq=bp+r, 0\leq r\leq p-1</math>
となるように整数 ''b'' , ''r'' を定めると
:<math>2aq=2bp+2r</math>
より <math>r<\frac{p}{2}</math> のとき <math>0\leq 2r<p</math> より <math>\left\lfloor\frac{2aq}{p}\right\rfloor=2b</math> となり、
一方 <math>r>\frac{p}{2}</math> のとき
:<math>2aq=(2b+1)p+(2r-p), 0<2r-p<p</math> より
<math>\left\lfloor\frac{2aq}{p}\right\rfloor=2b+1</math> となる。


== 相互法則の証明 ==

まず、次の補題を証明する。

'''補題''' <br />
:<math>\left\lfloor\frac{2aq}{p}\right\rfloor\equiv \left\lfloor\frac{(p-2a)q}{p}\right\rfloor\pmod{2}.</math>
'''証明''' <br />
''q'' は奇数だから
:<math>\left\lfloor\frac{2aq}{p}\right\rfloor\equiv q-1-\left\lfloor\frac{2aq}{p}\right\rfloor\pmod{2}</math>
が成り立つ。ところでこの左辺は
:<math>x\leq \frac{2aq}{p}</math>
が成り立つ正の整数 ''x'' の個数であるのに対し、右辺は
:<math>\frac{2aq}{p}<x\leq q-1</math>
が成り立つ整数 ''x'' の個数である。これは
:<math>\frac{2aq}{p}<x\leq q-1 \iff 1\leq x<q-\frac{2aq}{p}=\frac{(p-2a)q}{p}</math>
より、<math>\left\lfloor\frac{(p-2a)q}{p}\right\rfloor</math> に一致する。


ガウスの補題の変形において、和を<math>a<\frac{p}{4}, a>\frac{p}{4}</math> に分割し、後者に対して先程の補題を用いると
:<math>\sum_{a=0}^{\frac{p-1}{2}}\left\lfloor\frac{2aq}{p}\right\rfloor=\sum_{0\leq a<\frac{p}{4}}\left\lfloor\frac{2aq}{p}\right\rfloor+\sum_{\frac{p}{4}<a\leq\frac{p-1}{2}}\left\lfloor\frac{2aq}{p}\right\rfloor
=\sum_{0\leq a<\frac{p}{4}}\left\lfloor\frac{2aq}{p}\right\rfloor+\sum_{\frac{p}{4}<a\leq\frac{p-1}{2}}\left\lfloor\frac{(p-2a)q}{p}\right\rfloor</math>
となる。
:<math>\frac{p}{4}<a\leq\frac{p-1}{2} \iff 0\leq p-2a<\frac{p}{2}</math>
かつ <math>p-2a</math> は奇数であるから、上記の和は
:<math>\sum_{0\leq b\leq \frac{p-1}{2}, 2|b}\left\lfloor\frac{bq}{p}\right\rfloor+\sum_{0\leq b\leq\frac{p-1}{2}, b:\textrm{ odd}}\left\lfloor\frac{bq}{p}\right\rfloor
=\sum_{0\leq b\leq \frac{p-1}{2}}\left\lfloor\frac{bq}{p}\right\rfloor</math>
に一致する。ここから
:<math>\left(\frac{q}{p}\right)=(-1)^{\sum_{b=0}^{\frac{p-1}{2}}\left\lfloor\frac{bq}{p}\right\rfloor}</math>
が成り立つ。同様に、
:<math>\left(\frac{p}{q}\right)=(-1)^{\sum_{b=0}^{\frac{q-1}{2}}\left\lfloor\frac{bp}{q}\right\rfloor}</math>
が成り立つ。

ここで、
:<math>S(p, q)=\sum_{b=0}^{\frac{p-1}{2}}\left\lfloor\frac{bq}{p}\right\rfloor</math>
は
:<math>0\leq x<\frac{p}{2}, 0\leq y\leq \frac{xq}{p} \cdots (\#)</math>
となる整数の組 (''x'' , ''y'' ) の個数に一致する。
同様に
:<math>S(q, p)=\sum_{b=0}^{\frac{q-1}{2}}\left\lfloor\frac{bp}{q}\right\rfloor</math>
は
:<math>0\leq y<\frac{q}{2}, 0\leq x\leq \frac{yp}{q}</math>
となる整数の組 (''x'' , ''y'' ) の個数に一致する。
ここで
:<math>0\leq x\leq \frac{yp}{q} \iff x\geq 0, y\geq \frac{xq}{p}</math>
および
:<math>y<\frac{q}{2}, x\leq\frac{yp}{q}\Rightarrow x<\frac{p}{2}</math>
より、 <math>S(q, p)</math> は
:<math>\frac{xq}{p}\leq y<\frac{q}{2}, 0\leq x<\frac{p}{2} \cdots (\flat)</math>
となる整数の組 (''x'' , ''y'' ) の個数に一致する。ところで ''p'', ''q'' は相異なる素数なので <math>x<p</math> のとき <math>\frac{xq}{p}</math> は整数ではありえない。よって <math>(\#)</math> の範囲にある整数の組と <math>(\flat)</math> の範囲にある整数の組を合わせると、重複することなく <math>0\leq x<\frac{p}{2}, 0\leq x<\frac{q}{2}</math> の範囲にある整数の組全体と一致する。したがって
:<math>S(p, q)+S(q, p)=\frac{p-1}{2}\cdot\frac{q-1}{2}</math>
が成り立つ。これにより
:<math>\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{S(p, q)+S(q, p)}=(-1)^\frac{(p-1)(q-1)}{4}</math>
が証明された。

{{Nav}}

{{DEFAULTSORT:しよとうせいすうろん へいほうしようよのそうこほうそくのしようめい}}
[[Category:初等整数論|へいほうしようよのそうこほうそくのしようめい]]