平方剰余の相互法則（その１）

　さて、いよいよ平方剰余の相互法則です。平方剰余の相互法則は、オイラーにより予想されガウスが証明しました。ガウスは生涯にわたり7つの異なる証明を与えています。ガウスが初めて証明したのはガウス日誌によれば、1796年4月8日です。ガウスがある朝、目を覚ました刹那に、正17角形の作図可能性に気が付いたのがその年の3月30日ですので、その9日後に平方剰余の相互法則を初めて証明したことになります。そのときガウスは19歳でした。

平方剰余の相互法則

　次の法則を平方剰余の相互法則(quadratic reciprocity)といいます。

(平方剰余の相互法則）

　\(p,q\)を異なる2つの奇素数とするとき、次が成立する。 \[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]

平方剰余の相互法則の意味

　平方剰余の相互法則のうち、左辺の\( \left(\frac{q}{p}\right)\)は\(\bmod{p}\)において\(q\)が平方剰余か否かを表しています。すなわち、 \[ x^{2}\equiv q\pmod{p}\] が解がある場合が\(1\)、解がない場合が\(-1\)です。

　同様に、\( \left(\frac{p}{q}\right)\)は\(\bmod{q}\)において\(p\)が平方剰余か否かを表しています。すなわち、 \[ x^{2}\equiv p\pmod{q}\] が解がある場合が\(1\)、解がない場合が\(-1\)です。

　つまり、平方剰余の相互法則は、\(\bmod{p}\)の世界と\(\bmod{q}\)の世界に関係があることを示しています。この点は、次回、書きますが、これ自体驚くべきことです。

　平方剰余の相互法則の右辺の\(\frac{p-1}{2}\)は、\(p\equiv 1\pmod{4}\)のとき偶数です。また、\(p\equiv 3\pmod{4}\)のときは奇数です。したがって、右辺は、\(p,q\)のうちいずれか１つ、または、両方とも4で割ると1余る素数である場合には、＋1になります。逆に、両方とも4で割ると3余る素数である場合、-1になります。

　以上より、\(p,q\)のうちいずれか一方、または、両方とも4で割ると1余る素数である場合、次の2つの合同式の解の有無が一致することが分かります。（いずれかの合同式が解をもつ場合には、他方も解を持つ。いずれかの合同式が解をもたない場合は、他方も解をもたない。）

\[ x^{2}\equiv q\pmod{p}\] \[ x^{2}\equiv p\pmod{q}\]

　また、\(p,q\)のうち両方とも4で割ると3余る素数である場合、上の二つの合同式のうち、いずれか一方は解があり、他方は解がないことになります。

（例）\(p=3,q=5\)の場合 \[x^{2}\equiv 5\pmod{3}\] の解の有無と \[x^{2}\equiv 3\pmod{5}\] の解の有無は一致します。なお、 \[\begin{array}{rll} \left(\frac{3}{5}\right) &=\left(\frac{5}{3}\right) &(\text{平方剰余の相互法則}) \\ &=\left(\frac{2}{3}\right)\\ &=(-1)^{\frac{3^{2}-1}{8}} &(\text{第2補充法則})\\ &=-1 \end{array}\] ですので上の2つの合同式はともに解をもたないことが分かります。

（例）\(p=131,q=223\)とすると、どちらも4で割ると3余る素数ですので、2つの合同式 \[x^{2}\equiv 223 \pmod{131}\] \[x^{2}\equiv 131 \pmod{223}\] は、どちらか一方が解をもち、他方が解をもたないことが分かります。

実際 \[\begin{array}{rll} \left(\frac{131}{223}\right) &=-\left(\frac{223}{131}\right) &(\text{平方剰余の相互法則})\\ &=-\left(\frac{92}{131}\right) \\ &=-\left(\frac{2}{131}\right)^{2}\left(\frac{23}{131}\right) &(92=2^{2}23)\\ &=-\left(\frac{23}{131}\right) \\ &=\left(\frac{131}{23}\right) &(\text{平方剰余の相互法則})\\ &=\left(\frac{16}{23}\right) &(131-23\cdot5=16)\\ &=1 &(\text{16は平方数}) \end{array}\]

つまり、合同式 \[x^{2}\equiv 131 \pmod{223}\] は解をもち、合同式 \[x^{2}\equiv 223 \pmod{131}\] は解を持たないことが分かります。

　この計算から分かるとおり、平方剰余の相互法則を用いることにより、平方剰余か否かを効率的に判定することができます。このように平方剰余の相互法則は、実務的にも重要な意味を持っています。

　しかし、やはり驚くべきは、この式が\(\bmod{p}\)の世界と\(\bmod{q}\)の世界に関係があることを示していることだと思います。

　次回は、その点について書く予定です。