ソフィージェルマン素数とレピュニット数
今日は何の日
今日、11月11日はレピュニットの日です。
レピュニットとは、$11$や$11111$など$1$がいくつか並んだ自然数のことをいいます。
そのような数の中で、素数であるものをレピュニット素数といいます。例えば、$11$や$\underbrace{1111111111111111111}_{19個}$などがレピュニット素数になります。
$\underbrace{111111}_{6個}=111 \times 1001$や$\underbrace{111111111}_{9個}=111 \times 1001001$などの例から分かるように、$1$が合成数個並んでいる時、レピュニットは合成数になるのですが、$1$が素数個並んでいたとしてもレピュニットが素数であるとは限りません。例えば、$11111=41\times271$という例があります。
今回は、ある「特別な素数」個の$1$を並べたレピュニットが合成数であることを示します。
とある問題
まずは、以下のような問いから考えることにします。
自然数$ \underbrace{11 \cdots 11}_{41個} $は素数か？
以下に解答を記します。
↓
↓
↓
↓
↓
↓
↓
↓
解答
$\displaystyle \underbrace{11 \cdots 11}_{41個} = \underbrace{99 \cdots 99}_{41個} \cdot \frac{1}{9} = \frac{10^{41}-1}{9} $と変形出来る。
$$
\begin{eqnarray}
\left( \frac{10}{83} \right) &=& \left( \frac{2}{83} \right)\left( \frac{5}{83} \right) \\
&=& (-1) \cdot \left( \frac{83}{5} \right) \\
&=& (-1) \cdot \left( \frac{3}{5} \right) \\
&=& (-1) \cdot (-1) \\
&=& 1
\end{eqnarray}
$$であり、オイラーの規準により、$10^{41} \equiv 1 \pmod {83}$がいえる。
従って、$10^{41}-1$は$83$で割れるので、$\displaystyle \frac{10^{41}-1}{9}=\underbrace{11 \cdots 11}_{41個}$も$83$で割れるので、合成数である。
一般化
この問題を一般化する事で、以下のような定理が得られます。
$p$と$2p+1$が共に素数であり、$p \equiv 1,13,19 \pmod {20}$のとき、$\underbrace{11 \cdots 11}_{p個}$は$2p+1$で割り切れる。特に、$\underbrace{11 \cdots 11}_{p個}$は合成数である。
- $2p+1$ もまた素数であるような素数$p$のことをソフィージェルマン素数といいます。
$q=2p+1$とおく。このとき、$q \equiv 3,27,39 \pmod {40}$である。
まず、$\displaystyle \underbrace{11 \cdots 11}_{p個}=\underbrace{99 \cdots 99}_{p個} \cdot \frac{1}{9} = \frac{10^{p}-1}{9}$と変形する。$q \equiv 3,27 \pmod {40}$のとき、
$$
\begin{eqnarray}
\left( \frac{10}{q} \right) &=& \left( \frac{2}{q} \right)\left( \frac{5}{q} \right) \\
&=& (-1) \cdot \left( \frac{q}{5} \right) \\
&=& (-1) \cdot (-1) \\
&=& 1
\end{eqnarray}
$$であり、$q \equiv 39 \pmod {40}$のとき、
$$
\begin{eqnarray}
\left( \frac{10}{q} \right) &=& \left( \frac{2}{q} \right)\left( \frac{5}{q} \right) \\
&=& 1 \cdot \left( \frac{q}{5} \right) \\
&=& 1 \cdot 1 \\
&=& 1
\end{eqnarray}
$$であるから、結局$\displaystyle \left( \frac{10}{q} \right) = 1$である。従って、オイラーの規準より、
$$
10^p = 10^\frac{q-1}{2} \equiv \left( \frac{10}{q} \right) = 1 \pmod q
$$となるので、$10^p-1 \equiv 0 \pmod q$である。$q \neq 3$より、$q$と$9$は互いに素なので、$\displaystyle \frac{10^{p}-1}{9}$は$q=2p+1$の倍数である。また、$\displaystyle \frac{10^{p}-1}{9} > 2p+1 $であるから、$\displaystyle \frac{10^{p}-1}{9}$は合成数である。
おわりに
今回はオイラーの規準と平方剰余を上手く使うことによって、このような結果が得られました。
実はメルセンヌ数($2^n-1$($n$は自然数)という形の数)にも同様な定理が成り立ちます。
ソフィージェルマン素数$p$が$p \equiv 3 \pmod 4$を満たすとする。このとき、$2^p-1$は$2p+1$で割り切れる。
何故、似たような定理が成り立つのかというと、メルセンヌ数$2^n-1$の二進数表記が$\underbrace{11 \cdots 11}_{n個}$というようにレピュニットと同じ形をしているからです。つまり、二進数の世界においてのレピュニットは、メルセンヌ数だったのです！
最後まで読んでいただき、ありがとうございました！