数学大好き宣言！

勉強メモ。おもしろいことを探していきたい。

トップ > 数学 > 素数冪を法とした、多項式の反復合成

素数冪を法とした、多項式の反復合成

数学

f:id:mochi-mochi61:20211213073407p:plain
まずは次の定理を示す。
fを整係数多項式、pを素数、a,tを整数、kを自然数とすると、
f\left(a+t p^{k}\right) \equiv f(a)+t f^{\prime}(a) p^{k}\mod p^{k+1}
(証明)
多項式のテイラー展開より、ある整係数多項式g(x,y)が存在して、
f(x+y)=f(x)+f^{\prime}(x) y+g(x, y) y^{2}
あとはx=a, y=tpᵏ を代入すれば
f\left(a+t p^{k}\right) = f(a)+t p^k f^{\prime}(a) + (tp^k)^2 g(a,tp^k)
\equiv f(a)+t f^{\prime}(a) p^{k}\mod p^{k+1}

よって例えば
f^{2}\left(a+t p^{k}\right)\equiv f\left(f(a)+t f^{\prime}(a) p^{k}\right)\equiv f^{2}(a)+t\left(f^{\prime}(a)\right)^{2} p^{k}

繰り返し適用して、任意の自然数nに対して
f^{n}\left(a+t p^{k}\right)\equiv f^{n}(a)+t\left(f^{\prime}(a)\right)^{n} p^{k}\mod p^{k+1}

aが法pᵏで周期mの周期点、つまりfᵐ(a)≡a(mod pᵏ)で、 なおかつf'(a)≢0(mod p) なら、フェルマーの小定理より(f'(a))ᵖ⁻¹=1+pb(bは整数) だから、
f^{m(p-1)}\left(a+t p^{k}\right)\equiv f^{m(p-1)}(a)+t\left(f^{\prime}(a)\right)^{m(p-1)} p^{k}\equiv a+tp^{k}\mod p^{k+1}
よってa+tpᵏは任意のtで周期m(p-1) の周期点である。