循環小数の桁数と割り算について、補足

　だいぶ前の記事だけど、あれはわかりにくかったな……と思ったので、雑だけどわかりやすいまとめを書いておくよ。ただし、基礎知識がいる。

フェルマーの小定理 - Wikipedia

　まあ、これだけしかいらない。素数pに対して、1/pの循環小数表示を考えてみよう。このとき、10^{p-1}をpで割った余りは1である。とすると、1.0000000000...と、0がp-1個並んでいる数をpで割ると余りは0.00000...1の形になるはずだ。であれば、そのときの商は循環するはずである。なぜなら、0.00000...1をさらに割り算していけば、余りは0が倍に増えた0.0000000000...1という長い形になって、そのときの商は二回同じものが並ぶだろうからだ。もちろん、三回、四回……と何回も続けられるのだから、少なくとも素数pに対して1/pの小数展開はp-1桁で循環するはずである。
　この、1が最後に出てくる小数というのがミソで、つまりpで1.0000...を割り算していくと、必ず余りが0.0000...1の形になるわけだ。だから、0.0000...1の形になる最小の桁数が、循環部分の桁数である。
　以上を元に、1/pの循環部分が３桁になるpを求めてみよう。1.000を割り算して0.001という余りが出るのだから、このpは999の約数である。よって3か37になるが、3は１桁で循環するのでp=37のみが解。
　４桁もやってみよう。同じ理屈で、9999の約数のみが該当するので、3,11,101が候補になるが、3は１桁、11は２桁で循環するので、p=101のみが解。
　６桁もやろう。999999の約数のみが該当するので、3,7,11,13,37が候補になる。3は１桁、11は２桁、37は３桁で循環するからp=7,13が解。
　というわけで、このやり方でやれば循環小数の循環部分の桁数から素数pは簡単に割り出せるわけだ。やっぱフェルマーの小定理すげえな。
　え、素数じゃないときはどうするかって？
　そんな難しい話は僕は知らない。以上。