tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

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

一つ前の記事で「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の補題、そのものという感じですね!

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

 \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*}

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

面白い!!


 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 5444710013725792963322916526756467746442­08265246405598834086237345292487 \\
&\times 5971491762095304123607953914976573401599­4342199250253823083148168223296964916727­7637825641074323 \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 を考える必要があり、これが難しいわけですが。

とはいえ、LTEの補題の使いどころも分かってきて、面白かったですね!

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


参考サイト

11...11 (レピュニット) の素因数分解 - 素因数分解 - STUDIO KAMADA
stdkmd.net

指数持ち上げ補題 - INTEGERS
integers.hatenablog.com


追記(2021.05.26公開後)

冒頭に述べた通り、定理3についてはなんと2008年の東大の入試問題になっていたようです!
(探せばあるものですね・・・。ちょっぴり残念。)

https://matsubushi.com/2021/01/27/%E3%83%AC%E3%83%94%E3%83%A5%E3%83%8B%E3%83%83%E3%83%88%E6%95%B0%E3%81%AE%E6%80%A7%E8%B3%AA-2008%E5%B9%B4-%E6%9D%B1%E5%A4%A7%E3%83%BB%E7%90%86%E7%B3%BB/matsubushi.com

examist.jp