tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

法pにおける(-1)の平方根の計算(2)

4で割って1あまる素数  p に対して

 x^2 + 1 \equiv 0 \pmod{p} \tag{1}

をみたす整数  x が必ず存在することは「平方剰余の相互法則」の「第一補充則」と呼ばれ、よく知られていますね。


一方で、上の事実だけからは「 x がどのような数であるか」についてはわかりません。具体的に  x を求める方法はないのでしょうか。

実は以前にも似たような問題意識の記事を書いたことがありました。
tsujimotter.hatenablog.com

というわけで、今回はパート2です。

前回紹介したのは「オイラーの基準」を使った方法でしたが、今回は 「ウィルソンの定理」 を使った方法を紹介したいと思います。


ウィルソンの定理

ウィルソンの定理の主張だけを書いておきます。証明は初等整数論に関するいろいろな本に載っていますので、興味がある人は読んでみてください(参考文献の本にも書いてあります)

定理(ウィルソンの定理)
 p を素数とするとき、次が成り立つ:
 (p-1)! \equiv -1 \pmod{p}

 p から  1 引いた数の階乗をとると、 \bmod{p} -1 に合同になるという主張ですね。一般にこういうことが言えるのが面白いですね。

解答

 x = \left(\frac{p-1}{2}\right)! とすると合同式  (1) が成り立つことを示します。ウィルソンの定理の「ちょうど半分」ですね!


ウィルソンの定理の左辺を明示的に書くと

 (p-1)! = 1\cdot 2 \cdots (p-2)(p-1)

となります。

ここで、 p-k \equiv -k \pmod{p} となりますので、順番を入れ替えて  k (-k) のペアを作ります。この式変形が実に巧妙です。

 \displaystyle \begin{align} (p-1)! &\equiv (1\cdot (-1))\cdot (2 \cdot (-2)) \cdots \left(\frac{p-1}{2}\cdot \left(-\frac{p-1}{2}\right)\right) \\
& \equiv ( (-1) \cdot 1^2 )\cdot ( (-1) \cdot 2^2) \cdots \left( (-1)\cdot \left(\frac{p-1}{2}\right)^2\right) \\
& \equiv (-1)^{\frac{p-1}{2}} \cdot 1^2\cdot 2^2 \cdots \left(\frac{p-1}{2}\right)^2 \\
& \equiv (-1)^{\frac{p-1}{2}} \left(\left(\frac{p-1}{2}\right)!\right)^2
\end{align}

ここで、 p \equiv 1 \pmod{4} より、 \frac{p-1}{2} は偶数になります。したがって、 (-1)^{\frac{p-1}{2}} = 1 となりますから

 \displaystyle (p-1)! \equiv \left(\left(\frac{p-1}{2}\right)!\right)^2 \pmod{p}

が得られます。

一方、ウィルソンの定理より

 \displaystyle (p-1)! \equiv -1 \pmod{p}

ですから

 \displaystyle \left(\left(\frac{p-1}{2}\right)!\right)^2 \equiv -1 \pmod{p}

が成り立つというわけです。


言い換えると「 \left(\frac{p-1}{2}\right)! は法  p \equiv 1 \pmod{4} における  -1 の平方根である」というわけですね。

最後に定理の形でまとめておきましょう。

定理
 p p \equiv 1\pmod{4} なる素数とするとき、次が成り立つ:
 \displaystyle \left(\left(\frac{p-1}{2}\right)!\right)^2 \equiv -1 \pmod{p}

存在しか示されていなかった  x を具体的に求められるというのは気持ちがいいですね。

参考文献

今回の話は、以下の本の第1章を読んで知りました。本の内容自体も面白そうなので、この先も読んでみたいです。

関連記事

今回紹介した方法で  x^2 + 1 \equiv 0 \pmod{p} なる  x が得られると、 p = X^2 + Y^2 となる  X, Y の組を具体的に計算できるようになります。そんな方法を以下の記事で紹介しています。
tsujimotter.hatenablog.com