一つ前の記事で「LTEの補題(指数持ち上げ補題)」という有名な補題について勉強しました。せっかくなので、この補題を何か他のネタにも使えないかと考えました。
LTEの補題とは、こんな主張の補題でした:
これ自体の証明は、たとえば INTEGERSの記事 をご覧になってください。
色々考えていくうちに、レピュニットに応用できそうだ というところに思い至ったので、そのことについてまとめたのがこちらの記事です。
今回紹介するレピュニットの性質については、なかなか面白いと思います! なにせ、私はこの性質が載っているサイトを見たことがありません。
よかったらぜひ楽しんでいってください!
公開後に調べていたら、どうも定理3の話は東大の入試問題になっていたようです。東大すごいですね。(記事末尾にリンクを記載しています。)
今回の話で分かること
レピュニットとは、すべての桁に "1" が並ぶ整数のことです。たとえば
のような数がレピュニットです。
一般に を正の整数として、 桁のレピュニットを で表すと
のように表すことができます。等比数列の和公式を使うと
と表すこともできます。(この事実は今回たくさん使うので覚えておいてください。)
さて、今回考えたいのは、レピュニットが素数で何回割れるか という問題です。
特に、素数として を考えると
となります。( を選んだのは、 だからです。)
注目して欲しいのは、太字の部分です。 が で何回割れるかと、 が で何回割れるかが対応していることがわかります。
この後も ( と は互いに素)は でちょうど割れますし、( と は互いに素) は でちょうど割れます。面白いですね!
(これについては定理3で述べたいと思います。)
また、別のタイプの法則も見つけました。
というレピュニットは、素数 でちょうど 回割り切れますが、この事実から が でちょうど 回割りきれることがわかります。また、 は でちょうど 回割りきれることがわかります。以下、ずっと続きます。
他にも、 というレピュニットが素数 でちょうど 回割りきれるのですが、この事実から が でちょうど 回割り切れて、 が でちょうど 回割り切れることがわかります。
「なんじゃこりゃ」と思うかもしれませんが、こんな面白い(ヘンテコな?)性質を示すことに成功しました。(定理5で述べたいと思います。)
なお、今回の話は「10進レピュニット」に限定して考えていますが、まったく同じように「 進レピュニット」に拡張することができるので、興味ある人は考えてみてください。
桁のレピュニットは で何回割り切れるか?
肩慣らしに、まずは素数 についての「 桁のレピュニット 」について考えてみたいと思います。
下の方から を素因数分解していきましょう。
の素因数に着目すると、 自身で割り切れるのは のときだけであるように見えます。
実際、次の定理が成り立ちます。
より強く
が成り立つ。
(定理1の証明)
(i) のとき:
より、 である。
(ii) のとき:
基数を とすると(今回の場合は )、等比数列の和公式により
と表せる。
また、フェルマーの小定理より
である。 より が言えるので
を得る。
よって、 より
が得られる。したがって、 である。
ところで、定理1では「 の桁数 と割り切る素数 が一致する場合」を考えました。それ以外の の素因数 は、どのような形の素数になるのでしょうか。
となる素数 ()の条件を考えてみましょう。 なので自動的に であることに注意します。
のとき、次が言えます:
よって、次の定理が示されました:
素数 のときの 桁レピュニット の素因数は、かなり限定された形になるということですね。
レピュニット は で何回割り切れるか?
さらに考えを推し進めると、より一般的なケースについても考えることができそうです。
進レピュニットにおいては素数 が特異な例となるわけですが、特にこの場合は「LTEの補題」がドンピシャで使えるのです。
が成り立つ。
つまり、桁数 が で割れる回数が、そのまま を で割れる回数になっているというわけです。証明してみましょう。
(定理3の証明)
とすると、 より、 としてLTEの補題が適用できる。実際
が成り立つ。
一方、 の定義より
である。
見事にLTEの補題、そのものという感じですね!
そんなわけで、冒頭で紹介したように
のような例が成り立つことが分かってしまうわけですね!
面白い!!
桁のレピュニット
のときには、任意の に対して が完全に特定できました。最後に の場合についても考えてみましょう。
こちらは なので、LTEの補題がそのままでは使えません。そこで、いろいろ考える必要があります。
まず、次の定理が成り立ちます:
単純に が べきのときは、 で割り切れないというわけですね。この定理は、定理1のときと同じような方針で(フェルマーの小定理を使って)比較的簡単に示せます。
(定理4の証明)
フェルマーの小定理より として
この両辺を 乗すると
これは と より
と表せる。
同様に両辺を 乗すると
を得る。
繰り返し 乗することで、 に対して
が得られる。
ここで より なので
である。したがって
である。
より
が得られた。
定理4では ( べき)の形のレピュニットを考えましたが、より一般に「素因数に べきを持つ場合」について考えてみましょう。
かつ整数 を として、 が で割れるかを考えてみます。
ポイントになるのは、次の因数分解です:
つまり、因数分解の因子
①
②
について で割り切れるかどうかを調べればよいわけです。
①については、 における の位数を調べることに他なりません。 における の位数が の約数であれば、 は で割り切れることになりますね。
・・・でも、ちょっと待ってください。これってよく考えると当たり前のことを言っているんですよね。
なので、 が で割り切れることと、 が で割り切れることは同値だというわけです。
先ほどの因数分解によって
が得られるので、 ならば であることは明らかですね。
具体的に考えるともっと自明に思えると思います。たとえば、 は の倍数なので は を割り切りますよね。つまりそれだけの話をしているというわけです。
むしろ、もう一つの因子である
が で割り切れるか、の方が気になります。考察してみましょう。
ならば なので
ということになります。したがって
が言えたことになりますね。これはこれで面白いかも・・・?
もう少し精密に、次が言えそうです。
このとき、 に対して
が成り立つ。
(定理5の証明)
とすると
であることに注意する。最後の等式は等比数列の和公式を使った。
(i) のとき:
より かつ である。
特に より、 と に対して「LTEの補題」が適用できる。すなわち
が得られる。したがって
が成り立つ。
よって
が成立する。
(ii) のとき:
より である。等比数列の和公式より
である。フェルマーの小定理を繰り返し使って より、右辺は で割り切れない。よって、 が成立する。
面白そうな主張ではありますが、定理5の具体例を確認するのはなかなか大変そうです。
たとえば、 であることを使いましょう。 としているわけですね。
に対して( とした)定理5を適用すると、 が成り立つはずです。実際、計算してみると
となり、たしかに で 回割り切れることがわかりますね!
他にも、同じく を使うと、 に対しても が成り立つはずです。( とした。)
実際、レピュニットの素因数分解についてひたすら集められた このサイト によれば
となっていて、たしかに で 回割り切れることがわかります!
しかしながら、上の例は の例なので、まだ定理5の真の力を発揮している気がしません。
となるようなケースを頑張って探してみると、 という組を見つけることができました!
( としたというわけですね。)
に対して定理5を適用すると
が成立することになります。
実際、これが成り立つことは、合同式
によって確かめられます。(この計算は「繰り返し二乗法」によって確認済みです。)
よって正しいわけですが、なかなか凄まじい事実ですね。
(もはやここまでくると、 の素因数分解を愚直に実行しようとは思えませんね。)
ところで、突然出てきた という素数は一体なんなのでしょうか。今回使った性質のは
という性質でした。よくよく考えてみると、これは 基数 のヴィーフェリッヒ素数 の定義そのものですね!
まさかこんな風にヴィーフェリッヒ素数が出てくるとは思わなかったので、驚きました。
ちなみに、基数 のヴィーフェリッヒ素数は、次は だそうです。笑
おわりに
というわけで、今回は「レピュニットが素数で何回割れるのか問題」について、主に「LTEの補題」を活用して分析を行いました。
結構面白い性質が見つかったのではないかと思います!
- のときの (完全解決! )
- のときの ( を使って計算できる)
つまり であるような についての が分かれば、すべての に対して が分かるということになりますね。もちろん については となる を考える必要があり、これが難しいわけですが。
とはいえ、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