定理2.6で遊ぼう

概要

こちら の記事の定理2.6を少し拡張し, その式に具体的な集合, 写像を当てはめて面白そうな結果を導く.

定理2.6

定義0,1
$f:S\to S$を$n$回合成した写像を$f^n(x)$とする.
($f^0(x)=x$,$f^1(x)=f(x)$,$f^{n+1}(x)=f(f^n(x))$)

定義0,2
$A_S(f)$を$f(x)=x$を満たすような$S$の元$x$全体の集合
とする.

定理2,6
任意の集合$S$と写像$f:S\to S$について,
$p$が素数, $A_S(f)$,$A_S(f^p)$の要素数が有限のとき,
有限集合$T$の要素数を$|T|$と表すことにすると,
$|A_S(f^p)|\equiv |A_S(f)|(modp)$

上の定理は任意の正整数$n$について次のように拡張できる(証明にはメビウスの反転公式を用いる).

定理2.7

$$上の状況でn\mid \sum _{d\mid n,d>0}|A_S(f^d)|\mu (\frac{n}{d})である$$
$$特に|A_S(f^{p^k})|\equiv |A_S(f^{p^{k-1}})|(\mathrm{mod}{p}^k)$$
ただし$\mu (x)$は次の式で定義される関数(メビウス関数)である.
$$\mu (n)=\{\begin{array}{ll}0& (nは平方因子を持つ)\\ (-1{)}^t& (nは相異なるt個の素数の積で表せる(n=1のときt=0とする))\end{array}$$

素数全体の集合を$\mathbb{P}$とする. 以降注釈がない限り$p,q\in \mathbb{P}$とする.

オイラーの定理

定理2.7で$n=p^m(m\in \mathbb{N})$, $S=\mathbb{C}$, $f(x)=x^a(a\in \mathbb{N},a\ne 1)$とすると$A_S(f^k)=a^k$であるので
$$a^{p^m}\equiv a^{p^{m-1}}(\mathrm{mod}{p}^m)$$
特に$a$と$p$が互いに素のとき,
$$a^{p^{m-1}(p-1)}\equiv 1(\mathrm{mod}{p}^m)$$
また, オイラーのトーシェント関数$\varphi (x)$は乗法的関数で$\varphi (p^m)=p^{m-1}(p-1)$である.

$1$でない正整数$n$について, その素因数分解を$n=p_1^{q_1}{p}_2^{q_2}\cdots p_k^{q_k}$とすると, $\varphi (p_i^{q_i})\mid \varphi (n)$より
$$a\perp n\Rightarrow a^{\varphi (n)}\equiv 1(\mathrm{mod}{p}_i^{q_i})$$
がすべての$0<i\le k$について成り立つ. よって中国剰余定理より, $a\perp n$のとき

$$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$

ちょっとだけ一般化

$f(x)=x^a(a\in \mathbb{N},a\ne 1)$で$S$が整域のとき, $S$における$1$の$n$乗根の数を$r_n$とすると,
$$|A_S(f^n)|=r_{a^n-1}+1$$
である. よって
$$\sum _{d\mid n,d>0}|A_S(f^d)|\mu (\frac{n}{d})=\sum _{d\mid n,d>0}(r_{a^n-1}+1)\mu (\frac{n}{d})=\sum _{d\mid n,d>0}{r}_{a^n-1}\mu (\frac{n}{d})+\sum _{d\mid n,d>0}\mu (\frac{n}{d})$$
$$=\{\begin{array}{ll}\sum _{d\mid n,d>0}{r}_{a^n-1}\mu (\frac{n}{d})& (n\ne 1)\\ r_{a-1}+1& (n=1)\end{array}$$
となり, 結局
$$n\mid \sum _{d\mid n,d>0}{r}_{a^n-1}\mu (\frac{n}{d})$$
が得られる.

$(M_n({\mathbb{F}}_{p^m}){)}^{\times }$の元の位数について

$S={\mathbb{F}}_{p^m}^n,f(x)=Ax(A\in M_n({\mathbb{F}}_{p^m}))$のとき, $f^k(x)=A^{k}x$
よってこのとき$A_S(f^k)=Ker(A^k-I_n)$であるので$|A_S(f^k)|=(p^m{)}^{n-rank(A^k-I_n)}$となる.
定理2.7より
$$p^{m(n-rank(A^{q^k}-I_n))}\equiv p^{m(n-rank(A^{q^{k-1}}-I_n))}(\mathrm{mod}{q}^k)$$
特に$p\ne q$のとき, $(p^m{)}^t\equiv 1(\mathrm{mod}{q}^k)$となる最小の正整数$t$を$or{d}_{q^k}(p^m)$と表すと
$$n-rank(A^{q^k}-I_n)\equiv n-rank(A^{q^{k-1}}-I_n)(\mathrm{mod}or{d}_{q^k}(p^m))$$
$$rank(A^{q^k}-I_n)\equiv rank(A^{q^{k-1}}-I_n)(\mathrm{mod}or{d}_{q^k}(p^m))$$
$A$を$(M_n({\mathbb{F}}_{p^m}){)}^{\times }$の元と見たときの位数が$q^k$だったなら, これは
$A^{q^{k-1}}\ne I_nかつA^{q^k}=I_n$と同値である.
このとき、上式は$0\equiv rank(A^{q^{k-1}}-I_n)(\mathrm{mod}or{d}_{q^k}(p^m))$
しかし$A^{q^{k-1}}\ne I_n$より$rank(A^{q^{k-1}}-I_n)\ne 0$なので
$$n\ge rank(A^{q^{k-1}}-I_n)\ge or{d}_{q^k}(p^m)$$
群$G$に位数$a$の元$x$があり$b\mid a$ならば, $x^{\frac{a}{b}}$の位数は$b$であるので,
位数が$a$の倍数の元がある$\Rightarrow$位数$a$の元がある
が成り立つ.
よって
$$(M_n({\mathbb{F}}_{p^m}){)}^{\times }に位数がq^k(q\ne p)の元がある\Rightarrow n\ge or{d}_{q^k}(p^m)$$
となる. (対角化やジョルダン標準形を使えばもう少し強い主張が得られる. )