5
大学数学基礎解説
文献あり

ソフィー・ジェルマン素数とメルセンヌ数

1259
1
$$$$

経緯

以前、数学系の方たちと飲み会をしていたときに、ソフィー・ジェルマン素数の話になりました。その際、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$が合成数であることを判定するときに、この命題が役に立つんですかね?

追記(2021/1/9)

具体例

【初めてのJuliaプログラミング】ソフィー・ジェルマン素数を使ってメルセンヌ数の約数を求めてみた
※今回紹介した命題を使用して、具体例を計算した記事です。

よりシンプルな証明

ソフィー・ジェルマン素数とメルセンヌ数(よりシンプルな証明)
※本記事にてコメントを頂き、よりシンプルな証明を教えて頂きました。その証明を記載した記事です。

参考文献

[1]
加藤和也, 数論への招待
投稿日:20201120

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

みぽ
みぽ
156
28135
今日もねこがかわいい。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中