任意の素数はレピュニットの素因数に現れる（2, 5を除く）あとダイヤル数

Twitterって本当に面白いなと思うのですが、人々のいろんな発見が流れてくるのです。

私が最近面白いと思ったのは次のツイートです。

「2、5を除く全ての素数は11、111、1111、…の素因数として“周期的に”現れる」ってことに気が付いて、証明できた気がするんだけど、これって素数の研究に役立ったりしないかな。おれが気付ける程度のことだから既に知られているとは思うけど。
— Yukinari (@yukinarioshiro) 2020年8月27日

レピュニットについてはこれまでも何度か記事にまとめてきましたが、このツイートに書かれているような事実は知りませんでした。とても面白いと思いましたので、ぜひ紹介させてください。

レピュニット関連の記事はこちらから：
tsujimotter.hatenablog.com

今回の話はレピュニットだけでなく、「循環小数」や「ダイヤル数」という面白いテーマにも広がる話になっています。よろしければ最後までご覧になってください。

ツイートの主張の確認

上のツイートの内容について、必要な前庭知識をまとめておきましょう。

$11, \; 111, \; 1111$ のように $1$ が並ぶ数のことをレピュニットと呼びます。

また、 $n$ 桁のレピュニット

$\underbrace{111\ldots111}_{n\; \text{times}} \tag{1}$

を $R(n)$ と表すことにします。

このとき、次が成り立ちます：

定理

$2, 5$ を除く任意の素数 $p$ に対し、ある正整数 $n > 1$ が存在して $R(n)$ は $p$ で割り切れる。

実際、レピュニットの素因数を計算してみましょう：

$\begin{align} R(2) = 11 &= 11 \\ R(3) = 111 &= 3 \times 37 \\ R(4) = 1111 &= 11 \times 101 \\ R(5) = 11111 &= 41 \times 271 \\ R(6) = 111111 &= 3 \times 37 \times 7 \times 11 \times 13 \\ R(7) = 1111111 &= 239 \times 4649 \end{align}$

レピュニットのように巨大な数の素因数分解の計算においては、楕円曲線法を用いた素因数分解が便利です。こちらのページをお使いください：
tsujimotter.info

iPhoneをお持ちの方は「素数チェッカー」というアプリも便利に使えます：

素数チェッカ

Heart Solutions, Inc.
教育
無料

apps.apple.com

上で挙げた5つのレピュニットにおいて、素因数として

$3, \; 7, \; 11, \; 13, \; 37, \; 101, \; 239, \; 271, \; 4649$

という数が登場しました。

これ以外の素数は今の所まだ登場しませんが、 $R(8), \; R(9), \; R(10), \; \ldots$ と続けていけば、いつかは必ず登場するというのが上の定理の主張です。

とても面白いですね！

素因数の周期性

定理の証明に行く前に、レピュニットの数表についてもう少しだけ観察を続けます。

$R(4) = 1111$ は $11$ が $2$ 個並んだ数だと思うことができます。よって、 $11 \times 101$ と分解できます。これは $R(2) \times 101$ だと思うことができますね。

同様に、 $R(6) = 111111$ は $11$ が $3$ 個並んだ数だと思うことができます。すなわち、 $11 \times 10101 = R(2) \times 10101$ と思うことができます。

この調子で考えていくと、 $R(2)$ の素因数（つまり、 $11$ 自身）は、2個おきにレピュニットに現れることがわかりますね。

また、 $R(6) = 111111$ は $111$ が $2$ 個並んだ数だと思うことができます。すなわち、 $111 \times 1001 = R(3) \times 1001$ ということです。つまり、 $R(6)$ には $R(3)$ の素因数（ $3\times 37$ ）が登場することになります。

同様に、 $R(9) = 111111111$ は $111$ が $3$ 個並んだ数だと思うことができます。すなわち、 $111 \times 1001001 = R(3) \times 1001001$ ということです。実際、 $R(9)$ を素因数分解するとこうなります：

$R(9) = 111111111 = 3^2 \times 37 \times 333667$

ちゃんと $3$ と $37$ が素因数に登場しますね。

この調子で考えていくと、 $R(3)$ の素因数（ $3\times 37$ ）は、3個おきにレピュニットに現れることがわかりますね。

f:id:tsujimotter:20200830031908p:plain:w400

以上をまとめるとこういうことになります。

$R(n)$ で現れた素因数は $R(2n), \; R(3n), \; R(4n), \; \ldots$ でも現れる（周期性）

これもなかなか面白い性質ですね！

定理の証明

証明にあたっては、以下の２つのことが必要です：

レピュニット $R(n)$ を扱いやすい数式に落とす
$R(n)$ が $p$ を素因数に持つを合同式で表す

1. について考えてみましょう。 $R(n) = \underbrace{111\ldots111}_{n\; \text{times}}$ は

$R(n) = 1 + 10 + 10^2 + \cdots + 10^{n-1} \tag{2}$

と表すことができるでしょう。

右辺を等比数列の和だと思うと、

$\displaystyle R(n) = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{10-1} = \frac{10^n - 1}{9}$

と変形できますね。

この数が素数 $p$ を素因数に持つということは、 $\bmod{p}$ で $0$ に合同であるということです。すなわち

$\displaystyle R(n) = \frac{10^n - 1}{9} \equiv 0 \pmod{p} \tag{3}$

ということですね。これが 2. で述べたことです。

合同式に置き換えることができたら、あとは合同式のルールに乗っ取って変形していけば良いでしょう。

$p \neq 3$ であれば、式 $(3)$ の両辺に $9$ を掛けたものは、同値な合同式となります。したがって、以下では $p \neq 3$ としましょう。（ $p = 3$ はあとで個別に議論します。）

よって、 $p \neq 3$ において

$\displaystyle 10^n - 1 \equiv 0 \pmod{p}$

すなわち

$\displaystyle 10^n \equiv 1 \pmod{p} \tag{4}$

を満たす $n > 1$ の存在を示せば良いことになります。

ここまで来ると色々見えてきますね。フェルマーの小定理を使いましょう。フェルマーの小定理は、整数の合同式における議論で頻繁に用いられる定理ですので、ご存じない方はこれを機にぜひ覚えていってください。

フェルマーの小定理

整数 $a$ と素数 $p$ に対し、 $a$ と $p$ が互いに素であれば、次の合同式が成り立つ：

$a^{p-1} \equiv 1 \pmod{p} \tag{5}$

つまり、 $p$ と互いに素な $a$ は、 $\bmod{p}$ で $p-1$ 乗すると $1$ と合同になるということですね。

今回の問題は、 $10$ を $\bmod{p}$ で $n$ 乗したとき $1$ に合同になるような $n > 1$ は存在するかという問題でした。

$p \neq 2, 5$ のとき、 $10$ と $p$ は互いに素なので、 $a = 10$ としてフェルマーの小定理が使えます。すなわち、 $p \neq 2, 5$ のとき

$10^{p-1} \equiv 1 \pmod{p} \tag{6}$

が成り立ちます。

したがって、これまでの議論を踏まえて、 $p \neq 2, 3, 5$ であれば $n = p-1$ として $R(n)$ が素因数 $p$ を持つことが示されました。

なお、 $p = 3$ のときは、 $R(3) = 3 \times 37$ は明らかに素因数 $3$ を持つので成立します。

（証明終わり）

フェルマーの小定理が綺麗に決まって、面白いですね！

証明によって、素数 $p$ を素因数に持つ $R(n)$ の $n$ は、多くとも $p-1$ であることが分かりましたね。証明によってメカニズムがよく分かりましたね。

また、上で議論していませんが、 $R(n)$ の下一桁が $1$ であるため、 $p = 2, 5$ で割り切れるような $R(n)$ は存在しないことに注意しましょう。

ダイヤル数との関係

ここまでで本題の定理の証明は終わりなのですが、せっかくなのでレピュニットの問題を掘り下げた上で、関連する整数論の話題を紹介したいと思います。

前述の議論では「 $n = p-1$ で $R(n)$ が $p$ を素因数に持つ」という事実の証明について述べてきました。

一方で、たとえば $p = 37$ を見ると分かるように、

$R(3) = 3\times 37$

ですから、 $n = p-1 = 36$ よりもずいぶん前に $37$ が素因数に現れることがあります。

もちろん、 $R(36)$ においても $37$ は素因数に現れます。実際

$\begin{align} R(36) &= 111111111111111111111111111111111111 \\ &= 3^2 \times 7 \times 11 \times 13 \times 19 \times 37 \times 101 \times 9901 \times 52579 \times 333667 \times 999999000001 \end{align}$

となり、たしかに $37$ が素因数に現れていますね。

つまり、何が言いたいかというと、 $n = p-1$ で確かに $R(n)$ に素因数 $p$ が現れるわけですが、もっと早い $n$ でも素因数に現れる場合があるのです。というか、前に現れるケースの方が多いのです。

というわけで、以降では素数 $p$ に対して「 $R(n)$ が素因数 $p$ を持つような最小の整数 $n > 1$ 」を考えたいと思います。これを $n_p$ と書くことにしましょう。

実際、 $2, 3, 5$ を除く $100$ 以下の素数について、実験してみると次のようになります：

素数 $p$	$n_p$	$p-1$
$7$	$6$	$6$
$11$	$2$	$10$
$13$	$6$	$12$
$17$	$16$	$16$
$19$	$18$	$18$
$23$	$22$	$22$
$29$	$28$	$28$
$31$	$15$	$30$
$37$	$3$	$36$
$41$	$5$	$40$
$43$	$21$	$42$
$47$	$46$	$46$
$53$	$13$	$52$
$59$	$58$	$58$
$61$	$60$	$60$
$67$	$33$	$66$
$71$	$35$	$70$
$73$	$8$	$72$
$79$	$13$	$78$
$83$	$41$	$82$
$89$	$44$	$88$
$97$	$96$	$96$

ここで、色をつけた素数 $p = 7, 17, 19, 23, 29, 47, 59, 61, 97$ は、 $n_p = p-1$ であるような素数です。すなわち、最後の最後である $R(p-1)$ にならないと素因数に現れない「しぶとい素数」です。

さて、 $n_p$ はというと、合同式 $(4)$

$10^{n} \equiv 1 \pmod{p} \tag{4再掲}$

を満たす最小の $n > 1$ と思うことができます。
（つまり、10を何回冪乗したら1になるか、ということですね。）

このような $n$ のことを、 $\bmod{p}$ における $10$ の位数といいます。

$\bmod{p}$ における位数には、色々重要な性質があります。もっとも顕著な性質としては、位数は $p-1$ の約数であるということです。（実際、上の表を使って $n_p$ が $p-1$ の約数になっていることを確認してみましょう。）

このことは、フェルマーの小定理の帰結

$10^{p-1} \equiv 1 \pmod{p} \tag{6再掲}$

から直ちに導くことができます。

$p-1$ の約数の中で最大のものが $p-1$ 自身というわけですが、 $\pmod{p}$ の位数が $p-1$ であるような数を $\bmod{p}$ の原始根といいます。つまり、先ほどの「しぶとい素数」たち $p = 7, 17, 19, 23, 29, 47, 59, 61, 97$ において、 $10$ は $\bmod{p}$ の原始根だということですね。

このように問題を言い換えることで、整数論の世界のさまざまな知見が使えるのが面白いです。抽象化することで問題を水平展開できるのです。

最後に応用例として、循環小数とダイヤル数について紹介しましょう。

$p$ を相変わらず $p \neq 2, 3, 5$ であるような素数とします。このとき

$1/p$

という分数を考えて、これを小数展開しましょう。

この小数展開は、必ず有限の桁で循環します。たとえば、

$1/7 = 0.142857142857\ldots$ （6桁で循環する）
$1/11 = 0.0909\ldots$ （2桁で循環する）
$1/13 = 0.076923076923\ldots$ （6桁で循環する）

となります。循環する桁数を「循環節の長さ」ということにしましょう。

ここ重要な事実として、次のようなことが示せます：

$1/p$ の循環節の長さは、 $\bmod{p}$ における $10$ の位数に一致する

これは極めて面白い性質です。その理屈は、次のページを読んでいただければ分かるかと思います：
tsujimotter.hatenablog.com

今回の記事のレピュニットの性質を踏まえると、次の等式が成立することがわかりますね：

（ $R(n)$ が $p$ を素因数に持つような最小の $n > 1$ ）
＝（ $\bmod{p}$ における $10$ の位数）
＝（ $1/p$ の循環節の長さ）

特に循環節の長さが $p-1$ となるような $p$ に着目しましょう。

たとえば、 $1/7$ の小数展開は

$0.142857\ldots$

であり、 $142857$ が循環節です。この $142857$ には面白い性質があって、次のような式が成り立ちます：

$142857 \times 1 = 142857$

$142857 \times 3 = 428571$

$142857 \times 2 = 285714$

$142857 \times 6 = 857142$

$142857 \times 4 = 571428$

$142857 \times 5 = 714285$

$1$ から $6$ までの数をかけると、数が「巡回して」いるように見えるでしょう。
（読者の中には、電卓で上のような遊びをしたことある方も多いのではないでしょうか。）

$142857$ のような性質を持つ数のことをダイヤル数といいます。

ここで面白いのは、ダイヤル数はすべて $1/p$ の小数展開から作れるということです。これは次のような必要十分条件になっています：

ダイヤル数を循環節に持つ小数 $1/p$ は、循環節の長さが $p-1$ であるときに限られる

つまり、こういうことです：

$R(n)$ が $p$ を素因数に持つような最小の $n > 1$ が $p-1$ （しぶとい素数）
$\Longleftrightarrow$ $\bmod{p}$ における $10$ の位数が $p-1$ （10が $\bmod{p}$ の原始根）
$\Longleftrightarrow$ $1/p$ の循環節の長さが $p-1$
$\Longleftrightarrow$ $1/p$ の循環節がダイヤル数

これで「しぶとい素数」とダイヤル数がつながりましたね！面白い！

すなわち、先ほどの色をついた「しぶとい素数」

$p = 7, 17, 19, 23, 29, 47, 59, 61, 97$

においては、すべて $1/p$ の循環節がダイヤル数になるということです。

このような性質を持つ $p$ に名前がついているのか調べてみたのですが、どうやら "Full reptend primes" と呼ばれているようですね。
mathworld.wolfram.com

日本語の適切な訳は見つからなかったのですが、ご存知の方がいれば教えてください。

ところで、このような性質を持つ嬉しい素数 $p$ は無限に存在するのでしょうか？

実は、無限かどうかという問題は、現在未解決の予想となっています。アルティン予想という名前がついていますので、興味がある方はぜひ調べてみてください。

というわけで、いろんな方向に話が広がってしまいましたが、レピュニットから始まる整数論の世界を楽しんでいただけましたでしょうか？

レピュニットについては語り尽くしたと思っていましたが、まだまだ色々な発見がありそうです。

それでは今日はこの辺で！