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

初等整数論,ソフィージェルマン素数,素数

1306

経緯

以前、数学系の方たちと飲み会をしていたときに、ソフィー・ジェルマン素数の話になりました。その際、Wikipediaを調べてみたところ、以下のような性質が書かれていました。

ソフィー・ジェルマン素数 $p$ が $p \equiv 3 (\mod 4)$ を満たすとき、 $2 p + 1$ はメルセンヌ数 $2^{p} - 1$ の約数となる。

「簡単なmodの計算で証明できるかな？」と思いきや、私にはできませんでした。家に帰ってから、飲み会のときに教えて頂いたヒントを足掛かりにして証明してみました。

道具としては

フェルマーの小定理
平方剰余の相互法則

を用いました。

私自身、その飲み会に参加するまでソフィー・ジェルマン素数の存在すらも知らなかったので、教えて下さったみなさまに感謝です！

前提知識

ソフィー・ジェルマン素数

$2 p + 1$ が素数になるような素数 $p$ をソフィー・ジェルマン素数という。

フェルマーの小定理

$p$ を素数、 $a$ を $p$ の倍数ではない任意の整数であるとする。このとき、以下が成立する。
$a^{p - 1} \equiv 1 (\mod p)$

平方剰余の相互法則

$p, q$ を $2$ でない素数で相異なるものとすると
$(\frac{q}{p}) = (\frac{p}{q}) \cdot (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}$

本編

ソフィー・ジェルマン素数 $p$ が $p \equiv 3 (\mod 4)$ を満たすとする。
このとき
$2^{p} + 1 ≢ 0 (\mod 2 p + 1)$
が成り立つ。

ソフィー・ジェルマン素数 $p$ が $p \equiv 3 (\mod 4)$ を満たすとする。
$2^{p} + 1 \equiv 0 (\mod 2 p + 1)$
であると仮定して、背理法で証明する。

$\begin{aligned} 2^{p} & \equiv - 1 (\mod 2 p + 1) \\ \equiv - 1 + (2 p + 1) (\mod 2 p + 1) \\ \equiv 2 p (\mod 2 p + 1) \end{aligned}$
より
$\begin{aligned} 2^{p - 1} & \equiv p (\mod 2 p + 1) \dots ① \end{aligned}$
である。
（ $Z / (2 p + 1) Z$ が体であることを使いました）

$p \equiv 3 (\mod 4)$ より、 $p$ は奇素数なので、 $p - 1$ は偶数である。
よって、①より、 $p$ は、 $2 p + 1$ を法とする平方剰余である。

また
$\begin{aligned} 2 p + 1 & \equiv 1 (\mod p) \\ \equiv 1^{2} (\mod p) \end{aligned}$
より、 $2 p + 1$ は、 $p$ を法とする平方剰余である。

以上より
$(\frac{p}{2 p + 1}) = 1 (\frac{2 p + 1}{p}) = 1$
である。よって、平方剰余の相互法則より
$1 = 1 \cdot (- 1)^{\frac{p - 1}{2} \cdot \frac{2 p}{2}}$
であるので
$(- 1)^{\frac{p (p - 1)}{2}} = 1$
であることがわかる。したがって
$\frac{p (p - 1)}{2}$
は偶数である。

ここで、 $k$ を整数として、 $p = 4 k + 3$ とおくと
$\begin{aligned} \frac{p (p - 1)}{2} & = \frac{(4 k + 3) (4 k + 2)}{2} \\ = (4 k + 3) (2 k + 1) \end{aligned}$
となるが、これは奇数であるため、矛盾。

よって
$2^{p} + 1 ≢ 0 (\mod 2 p + 1)$
が成り立つ。

ソフィー・ジェルマン素数 $p$ が $p \equiv 3 (\mod 4)$ を満たすとき、 $2 p + 1$ はメルセンヌ数 $2^{p} - 1$ の約数となる。

ソフィー・ジェルマン素数 $p$ が $p \equiv 3 (\mod 4)$ を満たすとする。
$2$ と $2 p + 1$ は互いに素なので、フェルマーの小定理より
$2^{2 p} \equiv 1 (\mod 2 p + 1) \dots ①$
である。ここで
$\begin{aligned} 2^{2 p} - 1 & \equiv (2^{p} - 1) (2^{p} + 1) (\mod 2 p + 1) \end{aligned}$
であることと、①から
$\begin{array}{r} 2^{2 p} - 1 \equiv (2^{p} - 1) (2^{p} + 1) \equiv 0 (\mod 2 p + 1) \end{array}$
である。
ここで、補題より
$2^{p} + 1 ≢ 0 (\mod 2 p + 1)$
なので
$2^{p} - 1 \equiv 0 (\mod 2 p + 1)$
である。
よって、 $2 p + 1$ はメルセンヌ数 $2^{p} - 1$ の約数となる。