tsujimotterのノートブック

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

(自由研究)1/p^k型循環小数のフルサイクル性について

今日は

 \displaystyle \frac{1}{49}, \; \frac{1}{343}, \; \ldots

のような 「素数のべき乗分の1」の形の循環小数 について考えたいと思います。


実際、上記の小数を計算してみると

 \displaystyle \frac{1}{49} = 0.\overline{020408163265306122448979591836734693877551}
 \displaystyle \frac{1}{343} = 0.\overline{0029154518950437317784256559766763848396\ldots793}

となり、 1/4942桁 1/343294桁 と、たいへん長い循環節を持つことがわかります。これは後で見るように周囲の循環小数と比べてもかなり長いものとなっています。


この現象の裏には一体どのようなメカニズムが隠されているのでしょうか。

理屈を紐解いてみると、そこには  1/7 の循環節が ダイヤル数 になることが関係していることに気づきました。

とても面白い(きっと他では知られていない)定理を証明することができましたので、よろしければご覧になってください!

注:今回の記事はtsujimotter自身による独自研究をまとめたものです。内容の信ぴょう性についてはご自身でお確かめください。


2. きっかけ

先日10/23に開催された日曜数学会にて、すどさん( @ysmemoirs )という方が発表された「循環小数を九九のように並べる表」が今回のきっかけとなりました。


循環小数には以前から興味を持っていましたが、このような見せ方は考えたことがなく、目からウロコでした! この表はたいへん面白く、いくらでも眺められていられます。


この表を見て私が特に気になったのは、1/49の循環節の長さについてでした。循環節の長さが42桁と、周囲と比べて群を抜いて長くなっていますね。これはいったいどういうことなのでしょうか。


 49 という数は平方数であり、 49 = 7^2 と表せることから、 1/7 に関係した現象なのだなと思えます。この話を聞いていた物智さん( @butchi_y )が実験してみたところ、どうも  1/7^2 の他にも  1/7^3 1/7^4 も同様に、循環節の長さが長くなる傾向にあるようです。

 1/7^2(循環節の長さ  42
 1/7^3(循環節の長さ  294
 1/7^4(循環節の長さ  2058

とても長い循環節ですが、これは単に長いというだけではありません。ある意味で、これ以上長くなり得ないという、循環節の長さの限界点 となっているのです。

4節で詳しく理屈を説明しますが、 1/m の循環節の長さはオイラーのトーシェント関数  \varphi(m) の約数になることが知られています。

 p を奇数の素数として、 m = p^k とすると

 \varphi(p^k) = (p-1) p^{k-1} \tag{1}

となります。つまり、 1/p^k の循環節の長さが  (p-1) p^{k-1} に一致すれば、それは原理的に最長の長さということになるわけです。


実際、

 42 = (7-1)\cdot 7^{2-1}
 294 = (7-1)\cdot 7^{3-1}
 2058 = (7-1)\cdot 7^{4-1}

となることが確認できますので、確かに(前述の意味で)最長の循環節になっていますね。


以上の状況を表すために、以下の用語を定義しましょう。

定義(フルサイクル)
 m 10 と互いの素な正の整数とする。ここで、循環小数  1/m の循環節の長さが  \varphi(m) に一致するとき、 1/mフルサイクル であるという。

「フルサイクル」という用語はあくまで「このブログ限定の」ものであり、一般的にそのように呼ばれているわけではありません。

 1/p の循環節の長さが  \varphi(p) = p-1 に一致するときの素数  p を英語でFull reptend primeというそうです。

残念ながら、日本語の定訳がないのですが、Wikipediaでは「フルサイクルプライム」と呼ばれていました。ここから「フルサイクル」という語を拝借したという感じです。


ここで私が考えたのは、 1/7, 1/49, 1/343, 1/2401 のような現象は、もっと一般に成り立つのではないかということです。

つまり、素数  p について  1/p がフルサイクルであれば、 1/p^2, \; 1/p^3, \; 1/p^4, \; \ldots も同様にフルサイクルなのではないか、という予想です。


3. 実験と本日の主定理

実際、 1/p がフルサイクルになる最初の5つの素数  p = 7, \; 17, \; 19, \; 23, \; 29 について、循環節の長さを計算してみましょう。オイラーのトーシェント関数を比較すると、次のようになります。

 1/7^1 の循環節の長さ:  \mathbf{ 6 }, \;\;\;\;\;\; \varphi(7^1)  = \mathbf{ 6 }
 1/7^2 の循環節の長さ:  \mathbf{ 42 }, \;\;\;\;\;\; \varphi(7^2)  = \mathbf{ 42 }
 1/7^3 の循環節の長さ:  \mathbf{ 294 }, \;\;\;\;\;\; \varphi(7^3)  = \mathbf{ 294 }
 1/7^4 の循環節の長さ:  \mathbf{ 2058 }, \;\;\;\;\;\; \varphi(7^4)  = \mathbf{ 2058 }
 1/7^5 の循環節の長さ:  \mathbf{ 14406 }, \;\;\;\;\;\; \varphi(7^5)  = \mathbf{ 14406 }
 1/7^6 の循環節の長さ:  \mathbf{ 100842 }, \;\;\;\;\;\; \varphi(7^6)  = \mathbf{ 100842 }
 1/7^7 の循環節の長さ:  \mathbf{ 705894 }, \;\;\;\;\;\; \varphi(7^7)  = \mathbf{ 705894 }

 1/17^1 の循環節の長さ:  \mathbf{ 16 }, \;\;\;\;\;\; \varphi(17^1)  = \mathbf{ 16 }
 1/17^2 の循環節の長さ:  \mathbf{ 272 }, \;\;\;\;\;\; \varphi(17^2)  = \mathbf{ 272 }
 1/17^3 の循環節の長さ:  \mathbf{ 4624 }, \;\;\;\;\;\; \varphi(17^3)  = \mathbf{ 4624 }
 1/17^4 の循環節の長さ:  \mathbf{ 78608 }, \;\;\;\;\;\; \varphi(17^4)  = \mathbf{ 78608 }
 1/17^5 の循環節の長さ:  \mathbf{ 1336336 }, \;\;\;\;\;\; \varphi(17^5)  = \mathbf{ 1336336 }
 1/17^6 の循環節の長さ:  \mathbf{ 22717712 }, \;\;\;\;\;\; \varphi(17^6)  = \mathbf{ 22717712 }
 1/17^7 の循環節の長さ:  \mathbf{ 386201104 }, \;\;\;\;\;\; \varphi(17^7)  = \mathbf{ 386201104 }

 1/19^1 の循環節の長さ:  \mathbf{ 18 }, \;\;\;\;\;\; \varphi(19^1)  = \mathbf{ 18 }
 1/19^2 の循環節の長さ:  \mathbf{ 342 }, \;\;\;\;\;\; \varphi(19^2)  = \mathbf{ 342 }
 1/19^3 の循環節の長さ:  \mathbf{ 6498 }, \;\;\;\;\;\; \varphi(19^3)  = \mathbf{ 6498 }
 1/19^4 の循環節の長さ:  \mathbf{ 123462 }, \;\;\;\;\;\; \varphi(19^4)  = \mathbf{ 123462 }
 1/19^5 の循環節の長さ:  \mathbf{ 2345778 }, \;\;\;\;\;\; \varphi(19^5)  = \mathbf{ 2345778 }
 1/19^6 の循環節の長さ:  \mathbf{ 44569782 }, \;\;\;\;\;\; \varphi(19^6)  = \mathbf{ 44569782 }
 1/19^7 の循環節の長さ:  \mathbf{ 846825858 }, \;\;\;\;\;\; \varphi(19^7)  = \mathbf{ 846825858 }

 1/23^1 の循環節の長さ:  \mathbf{ 22 }, \;\;\;\;\;\; \varphi(23^1)  = \mathbf{ 22 }
 1/23^2 の循環節の長さ:  \mathbf{ 506 }, \;\;\;\;\;\; \varphi(23^2)  = \mathbf{ 506 }
 1/23^3 の循環節の長さ:  \mathbf{ 11638 }, \;\;\;\;\;\; \varphi(23^3)  = \mathbf{ 11638 }
 1/23^4 の循環節の長さ:  \mathbf{ 267674 }, \;\;\;\;\;\; \varphi(23^4)  = \mathbf{ 267674 }
 1/23^5 の循環節の長さ:  \mathbf{ 6156502 }, \;\;\;\;\;\; \varphi(23^5)  = \mathbf{ 6156502 }
 1/23^6 の循環節の長さ:  \mathbf{ 141599546 }, \;\;\;\;\;\; \varphi(23^6)  = \mathbf{ 141599546 }
 1/23^7 の循環節の長さ:  \mathbf{ 3256789558 }, \;\;\;\;\;\; \varphi(23^7)  = \mathbf{ 3256789558 }

 1/29^1 の循環節の長さ:  \mathbf{ 28 }, \;\;\;\;\;\; \varphi(29^1)  = \mathbf{ 28 }
 1/29^2 の循環節の長さ:  \mathbf{ 812 }, \;\;\;\;\;\; \varphi(29^2)  = \mathbf{ 812 }
 1/29^3 の循環節の長さ:  \mathbf{ 23548 }, \;\;\;\;\;\; \varphi(29^3)  = \mathbf{ 23548 }
 1/29^4 の循環節の長さ:  \mathbf{ 682892 }, \;\;\;\;\;\; \varphi(29^4)  = \mathbf{ 682892 }
 1/29^5 の循環節の長さ:  \mathbf{ 19803868 }, \;\;\;\;\;\; \varphi(29^5)  = \mathbf{ 19803868 }
 1/29^6 の循環節の長さ:  \mathbf{ 574312172 }, \;\;\;\;\;\; \varphi(29^6)  = \mathbf{ 574312172 }
 1/29^7 の循環節の長さ:  \mathbf{ 16655052988 }, \;\;\;\;\;\; \varphi(29^7)  = \mathbf{ 16655052988 }



たしかに、この例では循環節の長さとオイラーのトーシェント関数が一致しており、予想は成り立っていそうな気がします!!! 興奮してきました!!!


しかし興奮も束の間。せっかくなので、1000ぐらいまでやってみようと思い、計算してみると・・・

なんと、 p = 487 で反例が見つかってしまいました・・・。

 1/487^1 の循環節の長さ:  \mathbf{ 486 }, \;\;\;\;\;\; \varphi(487^1)  = \mathbf{ 486 }
 1/487^2 の循環節の長さ:  \mathbf{ 486 } , \;\;\;\;\;\; \varphi(487^2)  =  \mathbf{ 236682 }
 1/487^3 の循環節の長さ:  \mathbf{ 236682 }, \;\;\;\;\;\; \varphi(487^3)  =  \mathbf{ 115264134 }
 1/487^4 の循環節の長さ:  \mathbf{ 115264134 }, \;\;\;\;\;\; \varphi(487^4)  =  \mathbf{ 56133633258 }
 1/487^5 の循環節の長さ:  \mathbf{ 56133633258 }, \;\;\;\;\;\; \varphi(487^5)  =  \mathbf{ 27337079396646 }

 1/487^2 以降は、循環節の長さとオイラーのトーシェント関数の値が一致していませんね。

いやー、ざんねんです。せっかく新しい法則を発見したかと思ったのですが・・・。


しかし、どうにも諦めきれません。より詳細に調べてみたところ、どうも小さい素数  p においては、 p = 487 以外には反例がないようなのです。


あれ?もしかして、 p = 487 は特殊な例外なのでは?

 487 って、何か特殊な性質はなかったっけか?」

そう思って「  487」で検索してみると、なんとこれは (基数10の)ヴィーフェリッヒ素数 だったのです!


ここで2以上の整数  a について、基数  aヴィーフェリッヒ素数とは、

 a^{p-1} \equiv 1 \pmod{p^2} \tag{2}

を満たす素数  p のことです。

フェルマーの小定理により、一般に

 a^{p-1} \equiv 1 \pmod{p} \tag{3}

が成り立つことはわかりますが、1回だけでなくさらにもう1回  p で割れるような素数のことをヴィーフェリッヒ素数と呼ぶわけですね。

なお、基数  a = 10 のヴィーフェリッヒ素数は、今現在

 p =  3, \; 487, \; 56598313, \; \ldots

の3つが知られています。たまたま  1/487 がフルサイクルだったというのが今回の状況だったというわけです。ちなみに、ヴィーフェリッヒ素数が無限にあるかどうかは、未解決問題です。


このように考えると、基数10のヴィーフェリッヒ素数さえ除いてしまえば、予想はうまく成り立つのではないかと思えてきます。

そこで、次の予想を立てることにしました。

主定理(tsujimotter)
 p \neq 2, 5 を「基数10のヴィーフェリッヒ素数」ではない素数とする。このとき、 1/p がフルサイクルならば、 1/p^2, \; 1/p^3, \; 1/p^4, \ldots はすべてフルサイクルである。


「予想」といいましたが、なんとこの定理は証明することができます!! つまり、解決済み です!!

この証明を思いついたときは、興奮してしまってなかなか寝つけませんでした。


以下では、循環小数についての基本事項をおさらいして、この定理を実際に証明してみたいと思います!


4. 循環小数のおさらい

それでは、今回の証明に必要なレベルで、循環小数に関する最低限の事項をおさらいしたいと思います。

循環小数については、丁寧に描いたシリーズ記事もありますので、今回の記事でわからないことがあれば是非ご参照ください:
tsujimotter.hatenablog.com


まず、 1/m の循環節の長さが  \varphi(m)(最大)、すなわちフルサイクルであるという条件について考えます。このままでは扱いづらいですからね。


 1/m の割り算を筆算で考えるとき、 1.00000 という数を  10 倍しながら  m で割っていくことになります。ここで、 m で割ったあまりに  1 が再び現れるときが、ちょうど循環節の終わりとなります。

f:id:tsujimotter:20211024140244p:plain:w180

 1/7 の場合は、 1000000 = 10^6 ではじめて  7 で割ったあまりが  1 となるので、循環節の長さがちょうど  6 というわけです。


したがって、次が言えます:

( 1/m の循環節の長さ) =  ( 10^e \equiv 1 \pmod{m} となる最小の正整数  e)


一般に、 a m と互いに素な数として

 a^e \equiv 1 \pmod{m}

を満たす最小の正整数  e を「 \bmod{m} における  a の位数」といいます。これを  \operatorname{ord}_m(a) と表すことにしましょう。

すると、グレー枠内の式右辺は  \operatorname{ord}_m(10) と言い換えられます。

( 1/m の循環節の長さ) =    \operatorname{ord}_m(10)



一方、位数には上限があります。

 m に対するオイラーのトーシェント関数  \varphi(m) を考えると、次のオイラーの定理が成り立ちます。

定理(オイラーの定理)
 m と互いに素な  a に対して
 a^{\varphi(m)} \equiv 1 \pmod{m}

が成り立つ。


オイラーの定理から、 a = 10 m と互いに素であれば  10^{\varphi(m)} \equiv 1 \pmod{m} であると言えるので、ここから  \operatorname{ord}_m(10) \varphi(m) の約数になることがわかります。

つまり( 10 m と互いに素であれば) 1/m の循環節の長さは  \varphi(m) の約数になるというわけですね。そこで、循環節がちょうど最大である  \varphi(m) に一致するような  1/m をフルサイクルと呼ぶことにしたわけですね。



特に、 m = p(素数)のときには  \varphi(p) = p-1 となります。 10 と互いに素である素数  p \neq 2, 5 の場合、 1/p の循環節の長さは  p-1 の約数になります。

この記事では、 p が素数の場合は循環節の長さがちょうど  p-1 になっている  1/p をフルサイクルと呼んでいるわけですが、このとき循環節の数は ダイヤル数 になるのでした。ダイヤル数とはすなわち
 1/7 = 0.\overline{142857}
 3/7 = 0.\overline{428571}
 2/7 = 0.\overline{285714}
 6/7 = 0.\overline{857142}
 4/7 = 0.\overline{571428}
 5/7 = 0.\overline{714285}

のように、 k/p 1 \leq k \leq p-1)を計算するとき、各循環節の数は「 1/p の循環節を巡回させたもの」になっているものを言うのでした。



こんな風に「 \operatorname{ord}_m(10) = \varphi(m) であるか?」が今回の記事の焦点となるわけですが、そもそも任意の  \bmod{m} において位数  \varphi(m) の元は必ず存在するのでしょうか?

 \operatorname{ord}_m(10) は、群論的には「乗法群  (\mathbb{Z}/m\mathbb{Z})^\times における  \overline{a} の位数」と言い換えることができます。つまり、乗法群  (\mathbb{Z}/m\mathbb{Z})^\times において、位数  \varphi(m) の元が存在するか、という問題に置き換わるわけですね。

これは、 (\mathbb{Z}/m\mathbb{Z})^\times が巡回群であるという条件に他なりません。


 (\mathbb{Z}/m\mathbb{Z})^\times の構造は非常によく調べられていて、次の事実が知られています:

 (\mathbb{Z}/m\mathbb{Z})^\times が巡回群
 \;\; \Longleftrightarrow \;\; m = 2, \,4, \,p^k, \,2p^k p は奇素数、 k は正整数)

したがって、フルサイクルかどうかを考える上では、 m = 2, \,4, \,p^k, \,2p^k のケースだけ考えれば十分というわけですね。特に今回は  p^e のケースを考察するというわけです。


以上のことを踏まえると、元々示したかった主定理は、 \operatorname{ord} を用いて次のように言い換えることができるでしょう。

主定理(言い換え)
 (g, p)

  •  p \neq 2, 5 は基数  g のヴィーフェリッヒ素数ではない素数
  •  g p と互いに素な2以上の整数

であるような組とする。

このとき、 \operatorname{ord}_p(g) = p-1 ならば、 k \geq 2 なる整数に対して  \operatorname{ord}_{p^k}(g) = (p-1)p^{k-1} である。


特に  g = 10 のケースが元々示したかった定理です。あとで示すように、今回の証明は基数の取り方によらないので、一般の  g で示すことができます。


こうやって言い換えてみると、単なる循環小数の定理というよりも

巡回群  (\mathbb{Z}/p\mathbb{Z})^\times の生成元  g が、巡回群  (\mathbb{Z}/p^k\mathbb{Z})^\times の生成元にもなるか?

という、群論の問いに見えてきますね。なかなか面白くなってきました!


5. LTEの補題

主定理の証明を行う上で、キーとなる補題を先に紹介します。

補題1(LTEの補題)
 p を奇素数とする。 p \not\mid x p \not \mid y なる相異なる整数  x, y x-y \equiv 0 \pmod{p} を満たすとする。このとき、任意の正の整数  n に対して次が成り立つ:
 v_p(x^n - y^n) = v_p(x - y) + v_p(n) \tag{5}

ここで、 v_p(x) p x を割り切る最大の回数とする。


LTEの補題は、このブログでも何度か登場していますね。最近気付いたのですが、この補題はこの手の問題に対してはかなり強力な道具のようです。

証明はINTEGERSによる以下の記事をご参照ください。
integers.hatenablog.com


6. 主定理の証明

それでは、いよいよ主定理の証明を行いたいと思います。示すべき定理を再掲します。

主定理(言い換え・再掲)
 (g, p)

  •  p \neq 2, 5 は基数  g のヴィーフェリッヒ素数ではない素数
  •  g p と互いに素な2以上の整数

であるような組とする。

このとき、 \operatorname{ord}_p(g) = p-1 ならば、 k \geq 2 なる整数に対して  \operatorname{ord}_{p^k}(g) = (p-1)p^{k-1} である。


(主定理の証明)
まず、次の補題を示します:

補題2
主定理の条件のもと、 \operatorname{ord}_p(g) = p-1 ならば  \operatorname{ord}_{p^k}(g)
 p-1, \; (p-1)p, \; (p-1)p^2,  \; \ldots, \; (p-1)p^{k-1} \tag{6}

のいずれかの値をとる

(補題2の証明)
 e = \operatorname{ord}_{p^k}(g) とおくと、オイラーの定理より  e \mid \varphi(p^k) = (p-1)p^{k-1} である。

また、 g^{e} \equiv 1 \pmod{p^k} であるから、これを \bmod{p} して  g^{e} \equiv 1 \pmod{p} である。仮定より、 \operatorname{ord}_p(g) = p-1 であったから、 (p-1) \mid e が言える。

したがって、 e は式  (6) のいずれかに一致する。

(補題2の証明 終わり)


補題2により、 \operatorname{ord}_{p^k}(g) が、 0 \leq i \leq k-1 なる整数  i を用いて

 \operatorname{ord}_{p^k}(g) = (p-1)p^i \tag{7}

と書けることがわかりました。ここで、 i = k-1 であることが示せれば証明終了です。


以下、 0 \leq i < k-1 なる  i について、 g^{(p-1)p^i} \not \equiv 1 \pmod{p^k} であることを示したいと思います。

 g^{(p-1)p^{k-1}} \equiv 1 \pmod{p^k} はオイラーの定理より明らかに成り立つので、これにより  \operatorname{ord}_{p^k}(g) = (p-1)p^{k-1} が示されるというわけです。


 x = g^{p-1} y = 1 とすると、 x, y はともに  p で割り切れず、フェルマーの小定理より

 x - y = g^{p-1} - 1 \equiv 0 \pmod{p} \tag{8}

も成り立ちます。したがって、このような  x, y に対してLTEの補題が適用できます。


LTEの補題より、任意の正の整数  n について

 v_p(g^{(p-1)n}  - 1) = v_p(g^{(p-1)}  - 1) + v_p(n) \tag{9}

が成立します。特に、 n = p^i として

 v_p(g^{(p-1)p^i}  - 1) = v_p(g^{(p-1)}  - 1) + i \tag{10}

が成り立ちます。

ここで、 p が基数  g のヴィーフェリッヒ素数ではない という条件を思い出します。すると

 g^{p-1} \not\equiv 1 \pmod{p^2} \tag{11}

が成り立ちます。このことは、 v_{p}(g^{(p-1)}  - 1) = 1 であることを意味します。


これと  i < k-1 を踏まえると、式  (10)

 \begin{align} v_p(g^{(p-1)p^i}  - 1) &= v_p(g^{(p-1)}  - 1) + i \\
&< 1 + (k-1) \\
&= k \end{align}

と評価でき、 v_p(g^{(p-1)p^i}  - 1) < k が結論づけられます。

これは、 0 \leq i < k-1 なる  i に対して

 g^{(p-1)p^i} \not \equiv 1 \pmod{p^k} \tag{12}

であることを意味します。

したがって、 \operatorname{ord}_{p^k}(g) = (p-1)p^{k-1} であることが示されました。

(主定理の証明 終わり)


7. おわりに

そんなわけで、

 \require{cancel} \begin{align} p = &7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, \\
& 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, \\
& 433, 461, \cancel{487}, 491, 499, 503, 509, 541, 571, 577, 593, \ldots \end{align}

のような、ダイヤル数を生み出す(基数10のヴィーフェリッヒ素数ではない)素数  p を使えば

 1/p, \; 1/p^2, \; 1/p^3, \; 1/p^4, \; 1/p^5, \; \ldots

という無限に続く循環小数がフルサイクルになることが示せました。


循環小数の循環節の長さを一般に表すことは困難な問題であることは知っていましたので、まさかこんな無限の系列に対して循環節の長さを言い当てる法則があるなんて思いもしませんでした。

証明もなかなか面白くて、ヴィーフェリッヒ素数が出てきたり、LTEの補題という有名な補題を使ったり。この証明を思いついたときは、大変興奮しました!!

なお(ここではやりませんが)ヴィーフェリッヒ素数の場合も、 v_p(g^{p-1} - 1) を適切に評価することで明示的な式を得ることができます。

本当に循環小数は、奥が深くて面白いです!!


問題のきっかけを与えてくださったすどさん、物智さん、日曜数学会に感謝です! 最近、数学へのモチベが下がりつつあったので、日曜数学会で英気を養うことができ、楽しい日曜数学になりました!

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


追記:2021.10.24 20:30

記事公開後にご指摘いただいたのですが、INTEGERSの記事(今回の記事内で引用している記事)の中で、今回の主定理に相当する命題が証明されていました。以下の1.5, 1.6がその該当箇所となりますので、宜しければご参照ください。
integers.hatenablog.com