Number Theory の話題（Repunit Number と Zsigmondy’s Theorem）

今回も引き続き「Zsigmondy’s Theorem」（ジグモンディの定理）を取り上げます。

前回はジグモンディの定理の内容とその応用例についてご紹介しました。今回の主役は次の数列です。

『レピュニット数（Repunit Number）』 すべての桁が1$1$である自然数を「レピュニット数」という。 特にここではレピュニット数列{Rn}$\{R_n\}$を Rn=111…111n個$$R_n=\underset{n個}{\underbrace{111\dots 111}}$$ と定めることにする。

見慣れない数かもしれませんが、電卓で最も遊ばれやすい数の一つと言えるのではないでしょうか(笑)。余談ですが、「レピュニット」というのは（英語圏の）造語で、1$1$が繰り返すことから、

“repeat“+”unit“=”repunit“

というのが名前の由来です。

このレピュニット数は面白い性質を持っています。例えば、以下の等式を見て下さい。

割と有名な等式かもしれませんが、次の式のリストを見ると何だか神秘的にすら思われます。

12=1$1^2=1$
112=121${11}^2=121$
1112=12321${111}^2=12321$
11112=1234321${1111}^2=1234321$
111112=123454321${11111}^2=123454321$
1111112=12345654321${111111}^2=12345654321$
11111112=1234567654321${1111111}^2=1234567654321$
111111112=123456787654321${11111111}^2=123456787654321$
1111111112=12345678987654321${111111111}^2=12345678987654321$

---

さて、このレピュニット数を小さい順から並べた数列を「レピュニット数列」と名付けて調べてみます。まず一般項は次のようになります。

漸化式はとなります。一応、2$2$進法や3$3$進法でもレピュニット数を考えることはできますが、ここでは10$10$進法（10$10$を基底としたレピュニット）で考えます。

横道に逸れますが、偶数個の1$1$からなるレピュニット数について、以下の等式が成立します。

62−52=11$6^2-5^2=11$
562−452=1111${56}^2-{45}^2=1111$
5562−4452=111111${556}^2-{445}^2=111111$
55562−44452=11111111${5556}^2-{4445}^2=11111111$
555562−444452=1111111111${55556}^2-{44445}^2=1111111111$
5555562−4444452=111111111111${555556}^2-{444445}^2=111111111111$

　　　　⋮$⋮$

これは偶然という訳ではなく、

という関係が背景にあります。10n+1${10}^n+1$ という数は n−1$n-1$ 個の0$0$を1$1$で挟んだ見た目をした数ですから、これにRn$R_n$を乗じればR2n$R_{2n}$になることは明白ですね。

---

レピュニット数Rn$R_n$は以下のような性質を持ちます。

（A$\text{A}$）m∣n⟺Rm∣Rn$m\mid n⟺R_m\mid R_n$

（B$\text{B}$）m$m$とn$n$が互いに素 ⟺$⟺$ Rm$R_m$とRn$R_n$が互いに素

これらの性質は以下の（ほぼ自明な）関係式により導かれます。

あとはユークリッドの互除法や帰納法により証明可能です。なお、レピュニット数列の隣接２項が互いに素であることは（B$\text{B}$）の特別な場合に相当しますが、その証明は非常に易しく、漸化式すら使用しません。

また、レピュニット数には次のような性質もあります。

（C$\text{C}$）2$2$および5$5$を除く任意の素数に対して、レピュニット数となるような倍数が存在する

この命題は次のように言い換えることができます。

（C$\text{C}$′）レピュニット数には2$2$および5$5$以外の任意の素数を素因数にもつものが存在する

これはいわゆる「鳩の巣論法」（「ディリクレの引き出し論法」とも）によって示すことができますし、フェルマーの小定理を知っていれば瞬殺です。

因みにこのレピュニット数列は入試問題の題材にもなっており、2008年の東大前期入試において出題されています。最近では駿台予備校主催の2017年第2回東大実戦模試で扱われたようです。（2008年の東大の問題は個人的にオススメです）

---

レピュニット数には他にも色々と面白い性質が存在するのですが、ここからは本題に移ろうと思います。

再掲になりますが、ジグモンディの定理とは以下のようなものでした。

『ジグモンディの定理（Zsigmondy’s Theorem）』 a$a$とb$b$が互いに素な整数で a>b$a>b$ であるとき、任意の正の整数n$n$に対して、an−bn$a^n-b^n$ を割り切るが ak−bk$a^k-b^k$ (1≦k≦n−1)$(1\leqq k\leqq n-1)$ を割り切らないような素数（primitive prime divisor）が少なくとも１つ存在する。但し以下の例外を除く。 ・n=1$n=1$ かつ a−b=1$a-b=1$ のとき ・n=2$n=2$ かつ a+b$a+b$ が2$2$の冪のとき ・n=6$n=6$ かつ a=2$a=2$、b=1$b=1$ のとき

今回は和のバージョンは必要ありませんので割愛します。

ここで、以下にRn$R_n$の素因数分解の結果を示します。上記の命題（A$\text{A}$）～（C$\text{C}$）がちゃんと成立しているのが理解して頂けると思います。

---

1:1$1$
2:11$11$
3:3･37$3･37$
4:11･101$11･101$
5:41･271$41･271$
6:3･7･11･13･37$3･7･11･13･37$
7:239･4649$239･4649$
8:11･73･101･137$11･73･101･137$
9:3･3･37･333667$3･3･37･333667$
10:11･41･271･9091$11･41･271･9091$
11:21649･513239$21649･513239$
12:3･7･11･13･37･101･9901$3･7･11･13･37･101･9901$
13:53･79･265371653$53･79･265371653$
14:11･239･4649･909091$11･239･4649･909091$
15:3･31･37･41･271･2906161$3･31･37･41･271･2906161$
16:11･17･73･101･137･5882353$11･17･73･101･137･5882353$
17:2071723･5363222357$2071723･5363222357$
18:3･3･7･11･13･19･37･52579･333667$3･3･7･11･13･19･37･52579･333667$
19:1111111111111111111$1111111111111111111$
20:11･41･101･271･3541･9091･27961$11･41･101･271･3541･9091･27961$
21:3･37･43･239･1933･4649･10838689$3･37･43･239･1933･4649･10838689$
22:11･11･23･4093･8779･21649･513239$11･11･23･4093･8779･21649･513239$
23:11111111111111111111111$11111111111111111111111$
24:3･7･11･13･37･73･101･137･9901･99990001$3･7･11･13･37･73･101･137･9901･99990001$
25:41･271･21401･25601･182521213001$41･271･21401･25601･182521213001$
26:11･53･79･859･265371653･1058313049$11･53･79･859･265371653･1058313049$
27:3･3･3･37･757･333667･440334654777631$3･3･3･37･757･333667･440334654777631$
28:11･29･101･239･281･4649･909091･121499449$11･29･101･239･281･4649･909091･121499449$
29:3191･16763･43037･62003･77843839397$3191･16763･43037･62003･77843839397$
30:3･7･11･13･31･37･41･211･241･271･2161$3･7･11･13･31･37･41･211･241･271･2161$ ･9091･2906161$･9091･2906161$
31:2791･6943319･57336415063790604359$2791･6943319･57336415063790604359$
32:11･17･73･101･137･353･449･641･1409$11･17･73･101･137･353･449･641･1409$ ･69857･5882353$･69857･5882353$
33:3･37･67･21649･513239$3･37･67･21649･513239$ ･1344628210313298373$･1344628210313298373$
34:11･103･4013･2071723･5363222357$11･103･4013･2071723･5363222357$ ･21993833369$･21993833369$
35:41･71･239･271･4649･123551$41･71･239･271･4649･123551$ ･102598800232111471$･102598800232111471$
36:3･3･7･11･13･19･37･101･9901･52579･333667$3･3･7･11･13･19･37･101･9901･52579･333667$ ･999999000001$･999999000001$
37:2028119･247629013$2028119･247629013$ ･2212394296770203368013$･2212394296770203368013$
38:11･909090909090909091$11･909090909090909091$ ･1111111111111111111$･1111111111111111111$
39:3･37･53･79･265371653$3･37･53･79･265371653$ ･900900900900990990990991$･900900900900990990990991$
40:11･41･73･101･137･271･3541･9091･27961$11･41･73･101･137･271･3541･9091･27961$ ･1676321･5964848081$･1676321･5964848081$
41:83･1231･538987$83･1231･538987$ ･201763709900322803748657942361$･201763709900322803748657942361$
42:3･7･7･11･13･37･43･127･239･1933･2689$3･7･7･11･13･37･43･127･239･1933･2689$ ･4649･459691･909091･10838689$･4649･459691･909091･10838689$
43:173･1527791･1963506722254397$173･1527791･1963506722254397$ ･2140992015395526641$･2140992015395526641$
44:11･11･23･89･101･4093･8779･21649･513239$11･11･23･89･101･4093･8779･21649･513239$ ･1052788969･1056689261$･1052788969･1056689261$
45:3･3･31･37･41･271･238681･333667･2906161$3･3･31･37･41･271･238681･333667･2906161$ ･4185502830133110721$･4185502830133110721$
46:11･47･139･2531･549797184491917$11･47･139･2531･549797184491917$ ･11111111111111111111111$･11111111111111111111111$
47:35121409$35121409$ ･316362908763458525001406154038726382279$･316362908763458525001406154038726382279$
48:3･7･11･13･17･37･73･101･137･9901･5882353$3･7･11･13･17･37･73･101･137･9901･5882353$ ･99990001･9999999900000001$･99990001･9999999900000001$
49:239･4649･505885997$239･4649･505885997$ ･1976730144598190963568023014679333$･1976730144598190963568023014679333$
50:11･41･251･271･5051･9091･21401･25601$11･41･251･271･5051･9091･21401･25601$ ･182521213001･78875943472201$･182521213001･78875943472201$
51:3･37･613･210631･2071723･52986961$3･37･613･210631･2071723･52986961$ ･5363222357$･5363222357$ ･13168164561429877$･13168164561429877$
52:11･53･79･101･521･859･265371653$11･53･79･101･521･859･265371653$ ･1058313049･1900381976777332243781$･1058313049･1900381976777332243781$
53:107･1659431･1325815267337711173$107･1659431･1325815267337711173$ ･47198858799491425660200071$･47198858799491425660200071$
54:3･3･3･7･11･13･19･37･757･52579･333667$3･3･3･7･11･13･19･37･757･52579･333667$ ･70541929･1475966169･440334654777631$･70541929･1475966169･440334654777631$
55:41･271･1321･21649･62921･513239･83251631$41･271･1321･21649･62921･513239･83251631$ ･1300635692678058358830121$･1300635692678058358830121$

---

取り敢えずR55$R_{55}$までの素因数分解の結果を列挙しました。察しの良い方ならお気付きでしょうが、色付きの数字は「新出の素因数」です。ここでRn$R_n$の「新出の素因数」とは、Rn$R_n$の素因数のうち、R2、⋯、Rn−1$R_2、\cdots 、R_{n-1}$のそれぞれを素因数分解して得られる素因数のいずれにも該当しないようなものを指しています。上記のリストを見ると、どの項に対しても「新出の素因数」が存在することが予想できます。

「新出の素因数」と言えば”あの定理”がピンと来ますよね？

･･･そうです！この予想をジグモンディの定理を利用して解決してみましょう。

---

《証明》

Rn=10n−19$R_n={\displaystyle \frac{{10}^n-1}{9}}$ であり、任意のn$n$に対して 10n−1${10}^n-1$ は9$9$の倍数であるから、常にRn$R_n$は整数である。したがってRn$R_n$の素因数は 10n−1${10}^n-1$ の素因数から32$3^2$を除いたものに一致する。ここでジグモンディの定理より、 10n−1${10}^n-1$ には少なくとも一つの「primitive prime divisor」が存在するから、命題

「Rn (n≧2)$R_n(n\geqq 2)$の任意の項に対して「新出の素因数」が存在する」

は真である。

---

非常にあっさりと解決してしまいました。ジグモンディの定理恐るべし･･･。

因みに、レピュニット数のうち素数となるものを「レピュニット素数」というのですが、R2$R_2$、R19$R_{19}$、R23$R_{23}$、R317$R_{317}$、R1031$R_{1031}$、R49081$R_{49081}$、R86453$R_{86453}$、R109297$R_{109297}$、R270343$R_{270343}$、⋯$\cdots$（この中には「確率的素数」も含まれる）と、かなり疎らに点在しています。2017年12月現在、レピュニット素数が出現する規則性や、無数に存在するか、などに関してはほとんど分かっていません（勿論、命題（A$\text{A}$）や（B$\text{B}$）を考えれば、Rn$R_n$が素数となるのはn$n$が素数の場合に限ることは直ぐに分かりますが･･･）。

もう少し「新出の素因数」について見ていきましょう。

n$n$が素数のとき命題（B$\text{B}$）により、Rn$R_n$の素因数はすべて「新出の素因数」となります。そして3$3$を除くすべての「新出の素因数」はみな一様にmodn$modn$で1$1$に合同、つまり新出の素因数をp (≠3)$p(\ne 3)$とすると

が成立します。これは位数の性質により証明可能ですので、早速証明してみましょう。

---

《証明》

Rn$R_n$の「新出の素因数」をp$p$とする。p(≠2,5)$p(\ne 2,5)$についてフェルマーの小定理により

となる。n$n$はp$p$を法としたときの10$10$の「位数」であるから、ordp(10)=n${\text{ord}}_p(10)=n$ と書ける。これと

「 10k≡1(modp)⟺ordp(10)|k${10}^k\equiv 1(\mathrm{mod}p)⟺{\text{ord}}_p(10)|k$ 」

という定理により、

が言える。
n$n$は「位数」であるから、p−1≥n$p-1\ge n$が成り立つ。ここで k=p−1$k=p-1$ とすれば、（イ）$（\text{イ}）$より、

10p−1≡1(modp)⟺n|p−1$${10}^{p-1}\equiv 1(\mathrm{mod}p)⟺n|p-1$$

が言える。
これと（ア）$（\text{ア}）$より、レピュニット数Rn$R_n$の「新出の素因数」をp$p$とするとき、p−1$p-1$ がn$n$で割り切れることが示された。

---

これは高校数学のレベルを超えていますが、位数の性質さえ押さえていれば、やっていることはごく単純です。フェルマーの小定理が、指数部分と剰余を繋ぐ重要な道具であることが、ここでも再認識できますね。

 

●　　　●　　　●　　　●　　　●

 

今回の話題はなかなか興味深いテーマだったのではないでしょうか？数年前から興味を持っていた内容なので、いつかまとめたいと思っていました。文字に起こすとあっさりとしてしまいますが、こういう数学的事実の発見（或いは再発見）というのは非常にワクワクさせるものなのです。皆さんにも何か面白いテーマにアタックして数学する楽しさを味わって欲しいと思います。

ところで、今回のレピュニットは 10n−19${\displaystyle \frac{{10}^n-1}{9}}$ ですが、当然 5n−14${\displaystyle \frac{5^n-1}{4}}$ や 6n−15${\displaystyle \frac{6^n-1}{5}}$ などといった数列も同様に考察することができます。まだまだ興味が尽きませんね！