◆東京都の大学生 M.Kさんからの解答。
「P が２，５でないとき 10(P-1) - 1 は P で割り切れる」
の証明ができないので、これを要請しておく。
まず、☆素数の秘密１の解答と同様に、m,a を定め
2n,b,c のかわりに n,b とすると、
例えば
０．１２３４５６７８９４５６７８９…
では
m = 3
n = 6
a = 123
b = 456789
となる。
ここで
1 a b
--- = ---- + -------------(*)
P 10m 10m(10n-1)
だから同様に
(10n-1) は P で割り切れる。
(10n-1)
h = --------
P
とおくと(*)と比較して
a = 0
m = 0
b = h
とできる。
実際に割り算をすると
0 . b_1 b_2 … b_n …
________________________________
P ) 1 . 0 0 … 0 …
r_1
--------------------
r_2
-----------
r_n
ここで r_n は 10n を P で割った余りだから 1 であり、
明らかにここから循環が始まる。
1 <= k < n の自然数 k について r_k != 1 である。
なぜなら そうでないと仮定すると n ではなく
k から 循環が始まってしまうからである。
また r_1 から r_(n-1) の間に同じものがあったとすると
その間が循環することになるから、この間に同じものはない。
r は余りであるから 1 から P-1 の値を取る
(0 では割り切れてしまう)
1 / P ではこのうちの n 個しか現れない。
この n 個に含まれないある x をとり
x / P を計算して r'_1,r'_2, ... ,r'_n' が得られたとすると
r'_1 = x * 10 (mod P) /* 3本線が書けないので = にする */
r'_2 = r'_1 * 10 (mod P)
r'_k = r'_(k-1) * 10 (mod P)
と
r_1 = 1 * 10 (mod P)
r_2 = r_1 * 10 (mod P)
r_k = r_(k-1) * 10 (mod P)
より
r'_1 = x * r_1 (mod P) が成り立ち
r'_k = x * r_k (mod P) を仮定すると
r'_(k+1) = x * r_k * 10 (mod P)
= x * r_(k+1) (mod P) が成り立つから
r'_k = x * r_k (mod P)
このことから r'_n = x となり 1 <= k < n の k について
r'_k = x と仮定すると r'_k = x * r_k = x = x r_n (mod P)
1 <= r_k,r_n < P より r_k = r_n となり矛盾。
よって r'_n で初めて余りが x になるからここから循環が始まり
1 が x になったことを除いて r に成り立つことは r' にも成り立って
また r' にある数と r にある数は全て異なっている。
このことをまだ出てきてない数に繰り返すと
n 個の数の組がいくつか得られる。
ここで最初の要請を思い出すと
P が２，５でないとき 10(P-1) - 1 は P で割り切れる。
r_(p-1) = 1 であることが分かり
r_k = 1 となるのは k が n の倍数である時だから
p-1 は n で割り切れて商を q とすると
数の組は q 個得られる。
以上より得られる循環のパターンは P-1 / n となる
感想
秋休みの間ずっと数学から離れていた頭を起こして
何とかここまでできた。
どうしても最初の要請を証明できなかった。
#define MAX 100000
main() {
long a[MAX];
long i,j;
long b = 1;
for (i=2;i
◆東京都の大学生 M.Kさんからの解答（訂正版）。
実は
P が２，５でないとき 10(P-1)- 1 は P で割り切れる
を使う必要はなかったようだ。
>このことをまだ出てきてない数に繰り返すと n 個の数の組がいくつか得られる
P-1 を n で割ったときの余りを r とし
r !=0 と仮定すると
n 個の数の組を取った後にまだ r 個の数が残っていて
もう一度上のことを繰り返すとn 個の数の組が必ず取れるはずだが
r 個の数しかのこってないので矛盾。
よって
r = 0
>P-1 は n で割り切れて商を q とすると