ちょっとした問題 - 解説編 -

数学

先日のちょっとした問題 - 出題編 -の解説です。必然的にネタバレなので、まだ見たくない方はお気をつけ下さい。
（以下、ネタバレ回避の改行）
.
.
.
.
.
.
.
.
.
.

問1

問2で導入した記号N(p,k)を用いると、問題の内容は「N(29,k)が29の二乗の倍数になる最小のkは何か」ということになります。
さて、N(29,k)は定義から等比数列 29, 29 \times 100, 29 \times 100^2, \dots , 29 \times 100^{(k-1)}の総和として表わせますので、等比数列の和の公式によって
N(29,k) = \sum_{i=0}^{k-1} 29 \times 100^i = \frac{29 \times (100^k - 1)}{99}
となります。29と99は互いに素なので、N(29,k)が29の二乗の倍数であることは、100^k - 1が29の倍数であること、言い換えれば100^kを29で割った余りが1であることと同値です。後はそのようになる最小のkを頑張って計算すればよいのですが、普通に計算するよりも剰余演算*1の考え方を用いた方が楽に計算できます。つまり、
100^1 = 3 \times 29 + 13 \equiv 13 \quad \pmod{29}
100^2 \equiv 13^2 = 169 \equiv 24 \equiv -5 \quad \pmod{29}
100^3 \equiv 13 \times (-5) = -65 \equiv -7 \quad \pmod{29}
100^4 \equiv (-5)^2 = 25 \equiv -4 \quad \pmod{29}
100^5 \equiv 13 \times (-4) = -52 \equiv 6 \quad \pmod{29}
100^6 \equiv (-5) \times (-4) = 20 \equiv -9 \quad \pmod{29}
100^7 \equiv (-7) \times (-4) = 28 \equiv -1 \quad \pmod{29}
となり、7乗で初めて余りが-1となったので、その2乗、即ち14乗で余りが初めて1となります。以上より、問1の答えは「k = 14」です。

問2

pが10進数でn桁の素数であるとします。問2ではn = 1またはn = 2の範囲を考えていますが、後のことも考えて、以下しばらくはnの範囲の制限は忘れて話を進めます。
まず、問1と同様の考え方により、
N(p,k) = \sum_{i=0}^{k-1} p \times (10^n)^i = \frac{p \times ((10^n)^k - 1)}{10^n - 1}
となります（問1はp = 29、n = 2の場合）。ここで、状況は以下の二通りの場合に分かれます。

pが 10^n - 1を割り切らない場合

このとき、問1と同様の理由により、N(p,k)がpの二乗の倍数であることは、 (10^n)^k - 1がpの倍数であること、即ち (10^n)^kをpで割った余りが1であることと同値です。後はこのようになる最小の正の整数kがk = pである場合を探すことになりますが、結論から言いますとそのような場合は存在しません。その理由を説明します。
まず、 10^nがpで割り切れる場合（これはp = 2またはp = 5の場合です）には (10^n)^kをpで割った余りは決して1にはなりません。次に 10^nがpで割り切れない場合には、 (10^n)^kをpで割った余りは1からp-1までの範囲で循環するため、少なくともkがp-1以下の範囲に上記の数の余りが1となるものが一つは存在します。（この説明は群の考え方を暗に用いていますが、群の概念をご存じない方向けには、フェルマーの小定理*2によって (10^n)^{p-1} \equiv 1 \quad \pmod{p}なので最小のkはp-1を超えない、という説明もできます*3。）以上の理由から、件の条件を満たす最小のkがk = pとなることは（今考えている場合については）あり得ないことになります。

pが 10^n - 1を割り切る場合

つまり、 10^n \equiv 1 \quad \pmod{p}の場合です。この場合には、和の形でのN(p,k)の表示に立ち戻って考えます。N(p,k)がpの二乗の倍数であることは、 \sum_{i=0}^{k-1} (10^n)^iがpの倍数になることと同値ですが、上記のpの性質より
\sum_{i=0}^{k-1} (10^n)^i \equiv \sum_{i=0}^{k-1} 1^i \equiv k \quad \pmod{p}
なので、件の条件を満たす最小のkはk = pとなります。従って、今考えている場合に当てはまる素数pは全て求める素数となります。

問2の結論

以上の議論から、素数pが件の条件を満たすこととpが 10^n - 1を割り切ることは同値です。
今まではnの範囲を制限せずに考えましたが、問2ではn = 1またはn = 2の場合のみを考えればよいため、 10^1 - 1 = 9の約数となる（1桁の）素数pと 10^2 - 1 = 99の約数となる2桁の素数pがいくつあるか数えます。具体的にはp = 3またはp = 11がこのような素数の全てなので、問2の答えは「2個」です。

問3

上の議論によると、問3では22以下の範囲のnについて、 10^n - 1の約数となるn桁の素数pがいくつあるか数えればよいことになります。ここで1をn個並べてできる数を R_nと書くことにすると（例えば R_5 = 11111）、 10^n - 1 = 9 \times R_nとなります。従って、nが2以上のときは、条件を満たす素数pの候補は R_nのみということになります。つまり、（n = 1のときは問2で調べたようにp = 3が条件を満たすので、それに加えて） R_nが素数であるような2から22までの整数nがいくつ存在するか数えればよいことになります。
ここで定義した数 R_nは「レプユニット（repunit）」と呼ばれており（英語のページですが、例えばここを参照下さい）、素数であるレプユニット*4はnが22以下の範囲では R_2 = 11と R_{19}の二つのみであることが知られています（例えばここのページを参照下さい）。勿論、レプユニットについての予備知識が無くても、（手計算では厳しいと思いますが）コンピュータを用いればこのぐらいの範囲であれば自力で確認することも可能と思います。

というわけで、上の2個のレプユニット素数にp = 3を合わせて、問3の答えは「3個」です。

問4

これまでの議論をまとめると、件の条件を満たす素数pの総数は、素数であるレプユニット R_nの総数プラス1個（p = 3のぶん）、ということになります。
では、素数であるレプユニットは全部でいくつあるのか、そもそも有限個なのか無限個なのか、という話ですが・・・結論から言いますと、わかりません！どうやらレプユニット素数が無限個存在するかどうかは未解決問題らしいのです（情報元は上述したこちらのページ）・・・ごめんなさい石を投げないで下さい、思いつきで考えた問題が思いもよらず未解決問題に繋がったのが嬉しくて、つい載せちゃったんですよぅ。

というわけで、問4の正確な答えはまだ誰も知りません。もし問4が解けた方がおられましたら、当ブログにコメントをお寄せ下さらなくてよいので、是非論文にしてしかるべき論文誌に投稿なさって下さいませ。

おまけ

後から気付いたことなのですが、素数pが 10^n - 1を割り切らない場合、問2と同様の議論により、N(p,k)がpのm乗の倍数である（mは正の整数）ことは、 (10^n)^k - 1がpの(m-1)乗の倍数であること、即ち (10^n)^kを p^{m-1}で割った余りが1であることと同値です。さらにpが2でも5でもない場合には、 10^nと p^{m-1}は互いに素なので、オイラーの定理*5によって (10^n)^kを p^{m-1}で割った余りが1となる正整数kが存在します。
つまり、このような素数pに対しては、適切なkを選ぶことでN(p,k)が素因数pをいくらでも多く含むようにできることになります。例えば、29をたくさん繋げた数の中には、29の29乗の倍数も、29の2929乗の倍数も存在するということになります。ちょっと面白いと思いませんか？

*1:一例として、検索で偶然ヒットしたこちらのページを参照

*2:検索で偶然ヒットしたこちらのページなどを参照

*3:実のところ、本質的には群の考え方と大差ないのですが

*4:さっき検索したところ、素数である R_nだけを「レプユニット」と呼んでいるページがありましたが、どのくらい一般的な呼び名なのかは知りません

*5:検索で偶然ヒットしたこちらのページなどを参照