以前、数学系の方たちと飲み会をしていたときに、ソフィー・ジェルマン素数の話になりました。その際、Wikipediaを調べてみたところ、以下のような性質が書かれていました。
ソフィー・ジェルマン素数$p$が$p\equiv 3\pmod{4}$を満たすとき、$2p+1$はメルセンヌ数$2^p-1$の約数となる。
「簡単なmodの計算で証明できるかな?」と思いきや、私にはできませんでした。家に帰ってから、飲み会のときに教えて頂いたヒントを足掛かりにして証明してみました。
道具としては
を用いました。
私自身、その飲み会に参加するまでソフィー・ジェルマン素数の存在すらも知らなかったので、教えて下さったみなさまに感謝です!
$2p+1$が素数になるような素数$p$をソフィー・ジェルマン素数という。
$p$を素数、$a$を$p$の倍数ではない任意の整数であるとする。このとき、以下が成立する。
$$
a^{p-1} \equiv 1 \pmod{p}
$$
$p,q$を$2$でない素数で相異なるものとすると
$$
\biggl(\frac{q}{p}\biggr)=\biggl(\frac{p}{q}\biggr)\cdot(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}
$$
ソフィー・ジェルマン素数$p$が$p\equiv 3\pmod{4}$を満たすとする。
このとき
$$
2^p+1 \not\equiv 0 \pmod{2p+1}
$$
が成り立つ。
ソフィー・ジェルマン素数$p$が$p\equiv 3\pmod{4}$を満たすとする。
$$
2^p+1 \equiv 0 \pmod{2p+1}
$$
であると仮定して、背理法で証明する。
$$
\begin{align}
2^p &\equiv -1 \pmod{2p+1}\\
&\equiv -1+(2p+1) \pmod{2p+1}\\
&\equiv 2p \pmod{2p+1}
\end{align}
$$
より
$$
\begin{align}
2^{p-1} &\equiv p \pmod{2p+1} \quad \cdots ①
\end{align}
$$
である。
($\mathbb{Z}/(2p+1)\mathbb{Z}$が体であることを使いました)
$p\equiv 3\pmod{4}$より、$p$は奇素数なので、$p-1$は偶数である。
よって、①より、$p$は、$2p+1$を法とする平方剰余である。
また
$$
\begin{align}
2p+1 &\equiv 1 \pmod{p}\\
&\equiv 1^2 \pmod{p}
\end{align}
$$
より、$2p+1$は、$p$を法とする平方剰余である。
以上より
$$
\biggl(\frac{p}{2p+1}\biggr)=1\\
\biggl(\frac{2p+1}{p}\biggr)=1\\
$$
である。よって、平方剰余の相互法則より
$$
1=1\cdot (-1)^{\frac{p-1}{2}\cdot\frac{2p}{2}}
$$
であるので
$$
(-1)^{\frac{p(p-1)}{2}}=1
$$
であることがわかる。したがって
$$
\frac{p(p-1)}{2}
$$
は偶数である。
ここで、$k$を整数として、$p=4k+3$とおくと
$$
\begin{align}
\frac{p(p-1)}{2} &= \frac{(4k+3)(4k+2)}{2}\\
&=(4k+3)(2k+1)
\end{align}
$$
となるが、これは奇数であるため、矛盾。
よって
$$
2^p+1 \not\equiv 0 \pmod{2p+1}
$$
が成り立つ。
ソフィー・ジェルマン素数$p$が$p\equiv 3\pmod{4}$を満たすとき、$2p+1$はメルセンヌ数$2^p-1$の約数となる。
ソフィー・ジェルマン素数$p$が$p\equiv 3\pmod{4}$を満たすとする。
$2$と$2p+1$は互いに素なので、フェルマーの小定理より
$$
2^{2p}\equiv 1 \pmod{2p+1} \quad \cdots ①
$$
である。ここで
$$
\begin{align}
2^{2p}-1 &\equiv (2^p-1)(2^p+1) \pmod{2p+1}
\end{align}
$$
であることと、①から
$$
\begin{align}
2^{2p}-1 \equiv (2^p-1)(2^p+1)\equiv 0 \pmod{2p+1}
\end{align}
$$
である。
ここで、補題より
$$
2^p+1 \not\equiv 0 \pmod{2p+1}
$$
なので
$$
2^p-1 \equiv 0 \pmod{2p+1}
$$
である。
よって、$2p+1$はメルセンヌ数$2^p-1$の約数となる。
素人質問ですが、$2^p-1$よりも、$2p+1$の方が調べやすいと思うので、$2^p-1$が合成数であることを判定するときに、この命題が役に立つんですかね?
【初めてのJuliaプログラミング】ソフィー・ジェルマン素数を使ってメルセンヌ数の約数を求めてみた
※今回紹介した命題を使用して、具体例を計算した記事です。
ソフィー・ジェルマン素数とメルセンヌ数(よりシンプルな証明)
※本記事にてコメントを頂き、よりシンプルな証明を教えて頂きました。その証明を記載した記事です。