定理2.6で遊ぼう

概要

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

定理2.6

定義0,1
$f:S\rightarrow 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\rightarrow S$について,
$p$が素数, $A_S(f)$,$A_S(f^p)$の要素数が有限のとき,
有限集合$T$の要素数を$|T|$と表すことにすると,
$|A_S(f^p)|\equiv |A_S(f)|\hspace{6pt}(mod\hspace{4pt}p)$

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

定理2.7

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

素数全体の集合を$\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 \neq 1)$とすると$A_S(f^k) = a^k$であるので
$$a^{p^m} \equiv a^{p^{m - 1}} \pmod {p^m}$$
特に$a$と$p$が互いに素のとき,
$$a^{p^{m - 1}(p - 1)} \equiv 1 \pmod {p^m}$$
また, オイラーのトーシェント関数$\phi (x)$は乗法的関数で$\phi (p^m) = p^{m - 1}(p - 1)$である.

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

$$a^{\phi (n)} \equiv 1 \pmod n$$

ちょっとだけ一般化

$f(x) = x^a(a \in \mathbb{N}, a \neq 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})$$
$$= \left\{ \begin{array}{ll} \sum_{d \mid n, d > 0} r_{a^n - 1} \mu (\frac{n}{d}) & (n \neq 1) \\ r_{a - 1} + 1 & (n = 1) \end{array} \right. $$
となり, 結局
$$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 \hspace{4pt} , \hspace{2pt} f(x) = Ax(A \in M_n(\mathbb{F}_{p^m}))$のとき, $f^k(x) = A^kx$
よってこのとき$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))} \pmod {q^k}$$
特に$p \neq q$のとき, $(p^m)^t \equiv 1 \pmod {q^k}$となる最小の正整数$t$を$ord_{q^k}(p^m)$と表すと
$$n - rank(A^{q^k} - I_n) \equiv n - rank(A^{q^{k - 1}} - I_n) \pmod {ord_{q^k}(p^m)}$$
$$rank(A^{q^k} - I_n) \equiv rank(A^{q^{k - 1}} - I_n) \pmod {ord_{q^k}(p^m)}$$
$A$を$(M_n(\mathbb{F}_{p^m}))^{\times}$の元と見たときの位数が$q^k$だったなら, これは
$A^{q^{k - 1}} \neq I_n \hspace{4pt} かつ \hspace{4pt} A^{q^k} = I_n$と同値である.
このとき、上式は$0 \equiv rank(A^{q^{k - 1}} - I_n) \pmod {ord_{q^k}(p^m)}$
しかし$A^{q^{k - 1}} \neq I_n$より$rank(A^{q^{k - 1}} - I_n) \neq 0$なので
$$n \geq rank(A^{q^{k - 1}} - I_n) \geq ord_{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 \neq p)の元がある \Rightarrow n \geq ord_{q^k}(p^m)$$
となる. (対角化やジョルダン標準形を使えばもう少し強い主張が得られる. )