読者です 読者をやめる 読者になる 読者になる

Azel's Note

とある高校生の雑記帳。あらゆるテーマに対する、感覚と論理の双方向からのアプローチの記録。

『1,11,111,...の数列の中に、2017で割り切れる項が存在することを示せ』の2通りの解答と一般化。またそれに付随する考察。

数学 数学-整数

高校の数学の課題で、『1,11,111,…の数列の中に、2017で割り切れる項が存在することを示せ』というものが出題された。

受験数学についても純粋数学についても、僕は数論の経験が殆どなく、最初は全く見当がつかずかなり悩んだが、結論として、レピュニットについての面白い定理を得たので備忘録としてここに。

この記事の以下の文中において、 

{ \displaystyle a(n)=\sum_{k=1}^{n}10^{k-1}~~(n \in \mathbb{N}) }

と定義する。便宜のため、以下も書いておく。

{ \displaystyle a(n)=\frac{10^{n}-1}{10-1} }

この問題は添削課題のおまけとして、「解ける者のみで構わない」との但し書きをつけて出題されたものだった。 最初は手を出せないあまり、ペンさえ机に置いて考えていたが、鳩ノ巣原理を使えることに気が付いてからは簡単だった。 以下は証明その1。


一般に、自然数 { \displaystyle p}自然数 { \displaystyle q} で割った余り { \displaystyle r} は、{ \displaystyle 0 \leqq r \leqq q-1} をみたす。

故に、 { \displaystyle a(n) } を2017で割った余りは0,1,2,….,2016の2017パターンある。

この事実と鳩ノ巣原理より、{ \displaystyle a(1)} から{ \displaystyle a(2018)}までの2018項を考えたとき、2017で割った余りが等しい組が少なくとも1つある。

そのようなnの組を、 { \displaystyle (s,t)~~(s>t>0) } と考えたとき、

{ \displaystyle a(s)-a(t)=a(s-t) \ast 10^{t} }

であり、10と2017は互いに素であるから、{ \displaystyle a(s-t) } は2017を因数に持つ。 □


出題者の先生曰く、どうも数論の出来る人の間では有名な問で、この解法も有名らしい。閃いたときは興奮を覚えたが拍子抜けである。

上の証明によって、{\displaystyle a(1),\cdots,a(2017)}のいずれかが2017を因数に持つことは示せたが、ここで、具体的に{\displaystyle n}が幾らの時に2017を因数に持つのか、そして{\displaystyle 1\leqq n \leqq 2017}に幾つ在るのかをやはり知りたくなる。

証明しても面白いだろうが、直感的に、条件を満たす{ \displaystyle n}{\displaystyle 1\leqq n \leqq 2017}には1つしかないように思える。 厳密な証明より先に、この直感が正しいかどうかを知りたくなったので、まずCでスクリプトを書いて確かめてみたが、やはり{ \displaystyle n=2016}の場合のみのようである。尚、僕が個人的に数学を師事しているM先生もVBAで確認してくれたが、同様の結果だった。

もちろん、{ \displaystyle n\leqq2017}から飛び出せば、{ \displaystyle n}が2016の倍数の時は2017で割り切れる。これは明らかな事実なので説明は割愛。

そしてここで発生する疑問は、{\displaystyle n=2016}のときに割り切れることを、数学的にどう示すかだ。

これも全く手の付けようが無く、非常に悩んだが、突然の閃きによってフェルマーの小定理を用いた証明を得た。

思いついてしまえば簡単な証明なのだが、記憶の片隅にあった使い道の知れない定理が初めて役に立った証明だったので、自分では気に入っている。 以下証明。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10と2017は互いに素であり、2017は素数であるから、フェルマーの小定理より、

{\displaystyle 10^{2016} \equiv 1 \pmod{2017}}

1を移項して

{\displaystyle 10^{2016}-1 \equiv 0 \pmod{2017}}

辺々を10-1(要は9)で割って (ここで、9⊥2017)

{\displaystyle \frac{10^{2016}-1}{10-1} \equiv \pmod{2017}}

これは{\displaystyle a(2016)}が2017で割り切れることを示す。 □

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ここで重要なのはこの証明が2017に限った話ではないということだ。2,3,5を除く一般の素数においても同様の証明が可能だ。

3は9と互いに素でないこと、2と5は10と互いに素でないことが上の証明を不能にしているし、そもそも2と5の倍数はa(n)の集合には存在しないことは明らかだ。

つまり、上の証明を一般的に述べれば、『2,3,5でない素数をpとおくと、p-1桁のレピュニットはpで割り切れる』という定理を得たことになる。数論に興味がなかった僕にとっては、非常に新鮮で面白い。

フェルマーの小定理を用いて示せたということは、オイラーの定理を用いれば、当然、より一般的な定理が得られる。

証明は上と同様なので割愛し、結果のみを纏める。

『レピュニットの因数定理』…「2または5を因数に持たない自然数をmとすると、φ(m)桁のレピュニットはmで割り切れる。」

とても綺麗な定理だ。

尚ここで、φ(n)はオイラーのファイ関数である。 つまり、nと互いに素なn未満の自然数の個数に等しい。

ここでさらに疑問が生じる。

n=φ(m)は、a(n)がmで割り切れるような最小のnを満たすとは限らない。 もっとも小さい反例はm=11だ。 φ(11)=10だから、a(10)は確かに11を因数にもつが、a(2)=11であり、n=2が条件を満たす最小のnとなる。

数学好きなら、a(n)がmを因数に持つような最小のnはどのようなものかやはり気になるが、これはカーマイケルの定理を用いることで解決する。

カーマイケル関数は非常に奇妙で、扱いにくく、理解しにくい。 そのため、この場でカーマイケルの定理を用いた証明を示すことは差し控える。興味のある方は考えてみては如何だろうか。