ソフィージェルマン素数とレピュニット数

1486

今日は何の日

今日、11月11日はレピュニットの日です。

レピュニットとは、 $11$ や $11111$ など $1$ がいくつか並んだ自然数のことをいいます。

そのような数の中で、素数であるものをレピュニット素数といいます。例えば、 $11$ や $\underset{19 個}{\underset{⏟}{1111111111111111111}}$ などがレピュニット素数になります。

$\underset{6 個}{\underset{⏟}{111111}} = 111 \times 1001$ や $\underset{9 個}{\underset{⏟}{111111111}} = 111 \times 1001001$ などの例から分かるように、 $1$ が合成数個並んでいる時、レピュニットは合成数になるのですが、 $1$ が素数個並んでいたとしてもレピュニットが素数であるとは限りません。例えば、 $11111 = 41 \times 271$ という例があります。

今回は、ある「特別な素数」個の $1$ を並べたレピュニットが合成数であることを示します。

とある問題

まずは、以下のような問いから考えることにします。

自然数 $\underset{41 個}{\underset{⏟}{11 \dots 11}}$ は素数か？

以下に解答を記します。

↓

解答
$\underset{41 個}{\underset{⏟}{11 \dots 11}} = \underset{41 個}{\underset{⏟}{99 \dots 99}} \cdot \frac{1}{9} = \frac{10^{41} - 1}{9}$ と変形出来る。
$\begin{array}{rcl} (\frac{10}{83}) & = & (\frac{2}{83}) (\frac{5}{83}) \\ = & (- 1) \cdot (\frac{83}{5}) \\ = & (- 1) \cdot (\frac{3}{5}) \\ = & (- 1) \cdot (- 1) \\ = & 1 \end{array}$ であり、オイラーの規準により、 $10^{41} \equiv 1 (\mod 83)$ がいえる。
従って、 $10^{41} - 1$ は $83$ で割れるので、 $\frac{10^{41} - 1}{9} = \underset{41 個}{\underset{⏟}{11 \dots 11}}$ も $83$ で割れるので、合成数である。

一般化

この問題を一般化する事で、以下のような定理が得られます。

$p$ と $2 p + 1$ が共に素数であり、 $p \equiv 1, 13, 19 (\mod 20)$ のとき、 $\underset{p 個}{\underset{⏟}{11 \dots 11}}$ は $2 p + 1$ で割り切れる。特に、 $\underset{p 個}{\underset{⏟}{11 \dots 11}}$ は合成数である。

$2 p + 1$ もまた素数であるような素数 $p$ のことをソフィージェルマン素数といいます。

$q = 2 p + 1$ とおく。このとき、 $q \equiv 3, 27, 39 (\mod 40)$ である。
まず、 $\underset{p 個}{\underset{⏟}{11 \dots 11}} = \underset{p 個}{\underset{⏟}{99 \dots 99}} \cdot \frac{1}{9} = \frac{10^{p} - 1}{9}$ と変形する。 $q \equiv 3, 27 (\mod 40)$ のとき、
$\begin{array}{rcl} (\frac{10}{q}) & = & (\frac{2}{q}) (\frac{5}{q}) \\ = & (- 1) \cdot (\frac{q}{5}) \\ = & (- 1) \cdot (- 1) \\ = & 1 \end{array}$ であり、 $q \equiv 39 (\mod 40)$ のとき、
$\begin{array}{rcl} (\frac{10}{q}) & = & (\frac{2}{q}) (\frac{5}{q}) \\ = & 1 \cdot (\frac{q}{5}) \\ = & 1 \cdot 1 \\ = & 1 \end{array}$ であるから、結局 $(\frac{10}{q}) = 1$ である。従って、オイラーの規準より、
$10^{p} = 10^{\frac{q - 1}{2}} \equiv (\frac{10}{q}) = 1 (\mod q)$ となるので、 $10^{p} - 1 \equiv 0 (\mod q)$ である。 $q \neq 3$ より、 $q$ と $9$ は互いに素なので、 $\frac{10^{p} - 1}{9}$ は $q = 2 p + 1$ の倍数である。また、 $\frac{10^{p} - 1}{9} > 2 p + 1$ であるから、 $\frac{10^{p} - 1}{9}$ は合成数である。

おわりに

今回はオイラーの規準と平方剰余を上手く使うことによって、このような結果が得られました。
実はメルセンヌ数( $2^{n} - 1$ ( $n$ は自然数)という形の数)にも同様な定理が成り立ちます。

ソフィージェルマン素数 $p$ が $p \equiv 3 (\mod 4)$ を満たすとする。このとき、 $2^{p} - 1$ は $2 p + 1$ で割り切れる。

何故、似たような定理が成り立つのかというと、メルセンヌ数 $2^{n} - 1$ の二進数表記が $\underset{n 個}{\underset{⏟}{11 \dots 11}}$ というようにレピュニットと同じ形をしているからです。つまり、二進数の世界においてのレピュニットは、メルセンヌ数だったのです！