08/01/17 17:53:43
>>514
n|m ならば F(n)|F(m) であることに注意する
F(n) ≡ 0 (mod M) となる最小の n を n(M) とする
N = Π^{m}_{k=1} p^{a_k}_k と素因数分解されるとする
このとき Chinese Remainder Theorem より次が成り立つ
n(N) = LCM( n(p^{a_1)_{1}) , ... , n(p^{a_m)_{m}) )
従って求める自然数全体は n(N) の倍数全体となる
以上より、素数 p と自然数 a に対して n(p^a) を具体的に求めれば良い
n(p) を具体的に求めるのは大変なので、n(p^a) を n(p) を用いて表せ