自由研究：レピュニットが素数で何回割れるのか問題

一つ前の記事で「LTEの補題（指数持ち上げ補題）」という有名な補題について勉強しました。せっかくなので、この補題を何か他のネタにも使えないかと考えました。

LTEの補題とは、こんな主張の補題でした：

LTEの補題（指数持ち上げ補題）

$p$ を奇数の素数とする。 $p$ で割り切れない相異なる整数 $x, y$ が $x\equiv y \pmod{p}$ なる関係を満たすとき、任意の正の整数 $n$ に対して次が成り立つ：

$\operatorname{ord}_p(x^n - y^n) = \operatorname{ord}_p(x - y) + \operatorname{ord}_p(n)$

これ自体の証明は、たとえば INTEGERSの記事をご覧になってください。

色々考えていくうちに、レピュニットに応用できそうだというところに思い至ったので、そのことについてまとめたのがこちらの記事です。

今回紹介するレピュニットの性質については、なかなか面白いと思います！　なにせ、私はこの性質が載っているサイトを見たことがありません。

よかったらぜひ楽しんでいってください！

2021.05.26 公開後の追記：
公開後に調べていたら、どうも定理3の話は東大の入試問題になっていたようです。東大すごいですね。（記事末尾にリンクを記載しています。）

今回の話で分かること

レピュニットとは、すべての桁に "1" が並ぶ整数のことです。たとえば

$11$

$111$

$1111$

のような数がレピュニットです。

一般に $n$ を正の整数として、 $n$ 桁のレピュニットを $R_n$ で表すと

$\displaystyle \begin{align*} R_n &= \underbrace{111\ldots 111}_{n\,\text{times}} \\ &= 10^{n-1} + 10^{n-2} + \cdots + 10 + 1 \\ &= \sum_{i=0}^{n-1} 10^i \end{align*}$

のように表すことができます。等比数列の和公式を使うと

$\displaystyle R_n = \frac{10^n-1}{10-1}$

と表すこともできます。（この事実は今回たくさん使うので覚えておいてください。）

さて、今回考えたいのは、レピュニットが素数で何回割れるかという問題です。

特に、素数として $3$ を考えると

$\begin{align*} R_{\bf 3} &= 111 = {\bf 3}\times 37 \\ R_{\bf 3^2} &= 111111111 = {\bf 3^2}\times 37 \times 333667 \\ R_{2\times {\bf 3^2}} &= {\bf 3^2}\times 7 \times 11 \times 13 \times 19 \times 37 \times 52579 \times 333667\\ R_{{\bf 3^3}} &= {\bf 3^3}\times 37 \times 757 \times 333667\times 440334654777631 \end{align*}$

となります。（ $3$ を選んだのは、 $10 - 1 = {\bf 3}^2$ だからです。）

注目して欲しいのは、太字の部分です。 $n$ が $3$ で何回割れるかと、 $R_n$ が $3$ で何回割れるかが対応していることがわかります。

この後も $R_{3^4 m}$ （ $m$ と $3$ は互いに素）は $3^4$ でちょうど割れますし、 $R_{3^5 m}$ （ $m$ と $3$ は互いに素）は $3^5$ でちょうど割れます。面白いですね！
（これについては定理3で述べたいと思います。）

また、別のタイプの法則も見つけました。

$R_{2} = 11$ というレピュニットは、素数 $11$ でちょうど $1$ 回割り切れますが、この事実から $R_{2 \times 11^1}$ が $11$ でちょうど $2$ 回割りきれることがわかります。また、 $R_{2 \times 11^2}$ は $11$ でちょうど $3$ 回割りきれることがわかります。以下、ずっと続きます。

他にも、 $R_{486}$ というレピュニットが素数 $487$ でちょうど $2$ 回割りきれるのですが、この事実から $R_{486 \times 487^1}$ が $487$ でちょうど $3$ 回割り切れて、 $R_{486 \times 487^2}$ が $487$ でちょうど $4$ 回割り切れることがわかります。

「なんじゃこりゃ」と思うかもしれませんが、こんな面白い（ヘンテコな？）性質を示すことに成功しました。（定理5で述べたいと思います。）

なお、今回の話は「10進レピュニット」に限定して考えていますが、まったく同じように「 $x$ 進レピュニット」に拡張することができるので、興味ある人は考えてみてください。

$p$ 桁のレピュニットは $p$ で何回割り切れるか？

肩慣らしに、まずは素数 $p$ についての「 $p$ 桁のレピュニット $R_p$ 」について考えてみたいと思います。

下の方から $R_p$ を素因数分解していきましょう。

$\begin{align*} R_{2} &= 11 \;\;\;{\bf (\text{素数})} \\ R_{3} &= 111 = {\bf 3} \times 37 \\ R_{5} &= 11111 = 41 \times 271 \\ R_{7} &= 1111111 = 239 \times 4649 \\ R_{11} &= 11111111111 = 21649 \times 513239 \\ R_{13} &= 1111111111111 = 53 \times 79 \times 265371653 \\ R_{17} &= 11111111111111111 = 2071723 \times 5363222357 \\ R_{23} &= 11111111111111111111111 \;\;\;{\bf (\text{素数})} \\ &\vdots \end{align*}$

$R_p$ の素因数に着目すると、 $p$ 自身で割り切れるのは $p=3$ のときだけであるように見えます。

実際、次の定理が成り立ちます。

定理1

$p$ を素数とする。 $R_p$ が $p$ で割り切れるのは $p = 3$ のときだけである。

より強く

$\newcommand{\HLNO}{\unicode[\sans-serif,STIXGeneral]{x306E}} \operatorname{ord}_p(R_p) = \begin{cases} 1 & (p = 3\;\HLNO\text{とき}) \\ 0 & (p \neq 3 \; \HLNO\text{とき}) \end{cases}$

が成り立つ。

（定理1の証明）
(i) $p = 3$ のとき：

$R_3 = 3\times 37$

より、 $\operatorname{ord}_3(R_3) = 1$ である。

(ii) $p \neq 3$ のとき：
基数を $x$ とすると（今回の場合は $x = 10$ ）、等比数列の和公式により

$\displaystyle R_p = x^{p-1} + x^{p-2} + \cdots + x + 1 = \frac{x^p-1}{x-1}$

と表せる。

また、フェルマーの小定理より

$x^p \equiv x \pmod{p}$

である。 $p \neq 3$ より $x \not\equiv 1 \pmod{p}$ が言えるので

$x^{p} - 1 \not\equiv 0 \pmod{p}$

を得る。

よって、 $x - 1 \not\equiv 0 \pmod{p}$ より

$\displaystyle R_{p} = \frac{x^{p} - 1}{x - 1} \not\equiv 0 \pmod{p}$

が得られる。したがって、 $\operatorname{ord}_p(R_p) = 0$ である。

（定理1の証明終わり）

ところで、定理1では「 $R_p$ の桁数 $p$ と割り切る素数 $p$ が一致する場合」を考えました。それ以外の $R_p$ の素因数 $q$ は、どのような形の素数になるのでしょうか。

$q \mid R_{p}$ となる素数 $q$ （ $\neq p$ ）の条件を考えてみましょう。 $q\mid R_p$ なので自動的に $q \neq 2$ であることに注意します。

$q\neq 3$ のとき、次が言えます：

$\displaystyle \begin{align*} q \mid R_p \;\; & \Longleftrightarrow \;\; q \mid \frac{10^p - 1}{10-1} \\ & \Longleftrightarrow \;\; q \mid 10^p - 1 \;\;\;\;\;\; (\because q\not\mid 10-1) \\ & \Longleftrightarrow \;\; 10^p - 1 \equiv 0 \pmod{q} \\ & \Longrightarrow \;\; p \mid (q-1) \;\;\;\;\;\; (\because \text{フェルマー}\HLNO{小定理} \; 10^{q-1} \equiv 1 \pmod{q})\\ & \Longleftrightarrow \;\; q \equiv 1 \pmod{p} \end{align*}$

よって、次の定理が示されました：　

定理2

$p, q$ を素数とする。このとき、次が成り立つ：

$q \mid R_p \;\; \Longrightarrow \;\; q \equiv 1 \pmod{p} \;\;\text{または}\;\; q = 3$

素数 $p$ のときの $p$ 桁レピュニット $R_p$ の素因数は、かなり限定された形になるということですね。

レピュニット $R_n$ は $3$ で何回割り切れるか？

さらに考えを推し進めると、より一般的なケースについても考えることができそうです。

$10$ 進レピュニットにおいては素数 $p = 3$ が特異な例となるわけですが、特にこの場合は「LTEの補題」がドンピシャで使えるのです。

定理3

$n$ を正の整数とする。このとき

$\operatorname{ord}_3(R_{n}) = \operatorname{ord}_3(n)$

が成り立つ。

つまり、桁数 $n$ が $3$ で割れる回数が、そのまま $R_n$ を $3$ で割れる回数になっているというわけです。証明してみましょう。

（定理3の証明）
$x = 10$ とすると、 $x \equiv 1 \pmod{3}$ より、 $x = 10, \; y = 1$ としてLTEの補題が適用できる。実際

$\begin{align*} \operatorname{ord}_3(x^{n} - 1) = \operatorname{ord}_3(x - 1) + \operatorname{ord}_3(n) \end{align*}$

が成り立つ。

一方、 $R_{n}$ の定義より

$\displaystyle \operatorname{ord}_3(R_{n}) = \operatorname{ord}_3\left(\frac{x^{n} - 1}{x-1}\right) = \operatorname{ord}_3(n)$

である。

（定理3の証明終わり）

見事にLTEの補題、そのものという感じですね！

そんなわけで、冒頭で紹介したように

のような例が成り立つことが分かってしまうわけですね！

面白い！！

$p^e$ 桁のレピュニット $R_{p^e}$

$p = 3$ のときには、任意の $n$ に対して $\operatorname{ord}_p(R_n)$ が完全に特定できました。最後に $p \neq 3$ の場合についても考えてみましょう。

こちらは $x \not\equiv 1 \pmod{p}$ なので、LTEの補題がそのままでは使えません。そこで、いろいろ考える必要があります。

まず、次の定理が成り立ちます：

定理4

$p$ を素数とし、 $e$ を正の整数とする。 $p\neq 3$ のとき $R_{p^e}$ は $p$ で割り切れない。

単純に $n$ が $p$ べきのときは、 $p$ で割り切れないというわけですね。この定理は、定理1のときと同じような方針で（フェルマーの小定理を使って）比較的簡単に示せます。

（定理4の証明）
フェルマーの小定理より $x = 10$ として

$x^p \equiv x \pmod{p}$

この両辺を $p$ 乗すると

$(x^p)^p \equiv x^p \pmod{p}$

これは $(x^p)^p = x^{p^2}$ と $x^p \equiv x \pmod{p}$ より

$x^{p^2} \equiv x \pmod{p}$

と表せる。

同様に両辺を $p$ 乗すると

$x^{p^3} \equiv x \pmod{p}$

を得る。

繰り返し $p$ 乗することで、 $e > 0$ に対して

$x^{p^e} \equiv x \pmod{p}$

が得られる。

ここで $p \neq 3$ より $x - 1 \not\equiv 0 \pmod{p}$ なので

$x^{p^e} \equiv x \not \equiv 1 \pmod{p}$

である。したがって

$x^{p^e} - 1 \not\equiv 0 \pmod{p}$

である。

$x - 1 \not\equiv 0 \pmod{p}$ より

$\displaystyle R_{p^e} = \frac{x^{p^e} - 1}{x - 1} \not\equiv 0 \pmod{p}$

が得られた。

（定理4の証明終わり）

定理4では $n = p^e$ （ $p$ べき）の形のレピュニットを考えましたが、より一般に「素因数に $p$ べきを持つ場合」について考えてみましょう。

$p\neq 3$ かつ整数 $m$ を $(m, p) = 1$ として、 $R_{mp^e}$ が $p$ で割れるかを考えてみます。

ポイントになるのは、次の因数分解です：

$\begin{align*} R_{mp^e} &= \frac{x^{mp^e} - 1}{x - 1} \\ &= \frac{x^{m} - 1}{x-1} ( (x^{m})^{p^e -1} + (x^{m})^{p^e - 2} + \cdots + (x^{m}) + 1) \end{align*}$

つまり、因数分解の因子
① $x^m - 1$
② $(x^{m})^{p^e -1} + (x^{m})^{p^e - 2} + \cdots + (x^{m}) + 1$

について $p$ で割り切れるかどうかを調べればよいわけです。

①については、 $\bmod{p}$ における $x = 10$ の位数を調べることに他なりません。 $\bmod{p}$ における $10$ の位数が $m$ の約数であれば、 $R_{mp^e}$ は $p$ で割り切れることになりますね。

・・・でも、ちょっと待ってください。これってよく考えると当たり前のことを言っているんですよね。

$\displaystyle R_m = \frac{10^m - 1}{10 - 1}$

なので、 $10^m - 1$ が $p \neq 3$ で割り切れることと、 $R_m$ が $p\neq 3$ で割り切れることは同値だというわけです。

先ほどの因数分解によって

$R_{mp^e} = R_{m} \times ( (x^{m})^{p^e -1} + (x^{m})^{p^e - 2} + \cdots + (x^{m}) + 1)$

が得られるので、 $p\mid R_m$ ならば $p \mid R_{mp^e}$ であることは明らかですね。

具体的に考えるともっと自明に思えると思います。たとえば、 $6$ は $3$ の倍数なので $111$ は $111111$ を割り切りますよね。つまりそれだけの話をしているというわけです。

むしろ、もう一つの因子である

② $(x^{m})^{p^e -1} + (x^{m})^{p^e - 2} + \cdots + (x^{m}) + 1$

が $p$ で割り切れるか、の方が気になります。考察してみましょう。

$p \mid R_m$ ならば $10^m \equiv 1 \pmod{p}$ なので

$\begin{align*} (x^{m})^{p^e -1} + (x^{m})^{p^e - 2} + \cdots + (x^{m}) + 1 &\equiv 1 + 1 + \cdots + 1 + 1 \\ &\equiv p^e \\ &\equiv 0 \pmod{p} \end{align*}$

ということになります。したがって

$p \mid R_{m} \;\; \Longrightarrow \;\; p^2 \mid R_{mp^e}$

が言えたことになりますね。これはこれで面白いかも・・・？

もう少し精密に、次が言えそうです。

定理5

$p\neq 3$ とし、整数 $m$ を $(m, p) = 1$ であるようにとる。また、 $\operatorname{ord}_p( R_m ) = f \geq 0$ であるとする。

このとき、 $e > 0$ に対して

$\operatorname{ord}_p( R_{mp^e} ) = \begin{cases} f + e & (f > 0\; \HLNO\text{とき}) \\ 0 & (f = 0\; \HLNO\text{とき})\end{cases}$

が成り立つ。

（定理5の証明）
$x = 10$ とすると

$\displaystyle \begin{align*} R_{mp^e} &= R_{m} \times ( (x^{m})^{p^e -1} + (x^{m})^{p^e - 2} + \cdots + (x^{m}) ) \\ &= R_{m} \times \frac{(x^m)^{p^e} - 1}{x^m-1} \end{align*}$

であることに注意する。最後の等式は等比数列の和公式を使った。

(i) $f > 0$ のとき：
$\operatorname{ord}_p( R_m ) = f > 0$ より $p\neq 2$ かつ $\operatorname{ord}_p(x^m - 1) > 0$ である。

特に $x^m \equiv 1 \pmod{p}$ より、 $x^m$ と $1$ に対して「LTEの補題」が適用できる。すなわち

$\operatorname{ord}_p( (x^m)^{p^e} - 1) = \operatorname{ord}_p(x^m - 1) + e$

が得られる。したがって

$\displaystyle \operatorname{ord}_p\left(\frac{(x^m)^{p^e} - 1}{x^m - 1} \right) = e$

が成り立つ。

よって

$\displaystyle \operatorname{ord}_p(R_{mp^e}) = \operatorname{ord}_p(R_m) + \operatorname{ord}_p\left(\frac{(x^m)^{p^e} - 1}{x^m - 1} \right) = f + e$

が成立する。

(ii) $f = 0$ のとき：
$\operatorname{ord}_p( R_m ) = 0$ より $x^m \not\equiv 1 \pmod{p}$ である。等比数列の和公式より

$\displaystyle (x^{m})^{p^e -1} + (x^{m})^{p^e - 2} + \cdots + (x^{m}) + 1 = \frac{(x^m)^{p^e} - 1}{x^m - 1}$

である。フェルマーの小定理を繰り返し使って $(x^m)^{p^e} \equiv x^m \not\equiv 1 \pmod{p}$ より、右辺は $p$ で割り切れない。よって、 $\operatorname{ord}_p( R_{mp^e} ) = 0$ が成立する。

（定理5の証明終わり）

面白そうな主張ではありますが、定理5の具体例を確認するのはなかなか大変そうです。

たとえば、 $\operatorname{ord}_{11}( R_2 ) = 1$ であることを使いましょう。 $p = 11, \; f = 1, \; m = 2$ としているわけですね。

$R_{2\times 11^1}$ に対して（ $e = 1$ とした）定理5を適用すると、 $\operatorname{ord}_{11}( R_{2\times 11} ) = 2$ が成り立つはずです。実際、計算してみると

$R_{2\times 11} = {\bf 11^2} \times 23 \times 4093 \times 8779 \times 21649 \times 513239$

となり、たしかに $11$ で $2$ 回割り切れることがわかりますね！

他にも、同じく $\operatorname{ord}_{11}( R_2 ) = 1$ を使うと、 $R_{2\times 11^2}$ に対しても $\operatorname{ord}_{11}( R_{2\times 11^2} ) = 3$ が成り立つはずです。（ $e = 2$ とした。）

実際、レピュニットの素因数分解についてひたすら集められたこのサイトによれば

$\begin{align*} R_{2\times 11^2} = &{\bf 11^3} \times 23 \times 4093 \times 4357 \times 8779 \times 15973 \times 21649 \\ &\times 25169 \times 38237 \times 274187 \times 513239 \times 1485397 \\ &\times 102502981431359171598893 \\ &\times 544471001372579296332291652675646774644208265246405598834086237345292487 \\ &\times 597149176209530412360795391497657340159943421992502538230831481682232969649167277637825641074323 \end{align*}$

となっていて、たしかに $11$ で $3$ 回割り切れることがわかります！

しかしながら、上の例は $f = 1$ の例なので、まだ定理5の真の力を発揮している気がしません。

$f \geq 2$ となるようなケースを頑張って探してみると、 $\operatorname{ord}_{487}( R_{486} ) = 2$ という組を見つけることができました！
（ $p = 487, \; f = 2, \; m = 486$ としたというわけですね。）

$R_{486\times 487^2}$ に対して定理5を適用すると

$\operatorname{ord}_{487}( R_{486 \times 487^2} ) = 4$

が成立することになります。

実際、これが成り立つことは、合同式

$10^{486 \times 487^2} \equiv 1 \pmod{487^4}$ かつ $10^{486 \times 487^2} \not\equiv 1 \pmod{487^5}$

によって確かめられます。（この計算は「繰り返し二乗法」によって確認済みです。）

よって正しいわけですが、なかなか凄まじい事実ですね。
（もはやここまでくると、 $R_{486 \times 487^2}$ の素因数分解を愚直に実行しようとは思えませんね。）

ところで、突然出てきた $487$ という素数は一体なんなのでしょうか。今回使った性質のは

$10^{487-1} \equiv 1 \pmod{487^2}$

という性質でした。よくよく考えてみると、これは基数 $10$ のヴィーフェリッヒ素数の定義そのものですね！

Wieferich prime - Wikipedia

まさかこんな風にヴィーフェリッヒ素数が出てくるとは思わなかったので、驚きました。

ちなみに、基数 $10$ のヴィーフェリッヒ素数は、次は $56598313$ だそうです。笑

おわりに

というわけで、今回は「レピュニットが素数で何回割れるのか問題」について、主に「LTEの補題」を活用して分析を行いました。

結構面白い性質が見つかったのではないかと思います！

$p = 3$ のときの $\operatorname{ord}_p(R_n)$ 　（完全解決！　）
$p\neq 3$ のときの $\operatorname{ord}_p(R_{mp^e})$ 　（ $\operatorname{ord}_p(R_m)$ を使って計算できる）

つまり $p \not \mid m$ であるような $R_m$ についての $\operatorname{ord}_p( R_m )$ が分かれば、すべての $n$ に対して $\operatorname{ord}_p( R_n )$ が分かるということになりますね。もちろん $p \not \mid m$ については $10^m \equiv 1 \pmod{p^f}$ となる $m$ を考える必要があり、これが難しいわけですが。