AMC day4 自分自身との合成写像でフェルマーの小定理

まえがき

本記事はAMC2022(Advent Math Calendar2022)という企画に参加するにあたって、数弱の筆者がどうにかネタを絞り出し作ったものです。他の参加者の顔ぶれがえぐすぎる...。もしこの記事を面白いと思っていただけたのなら、筆者にこのような記事を書く機会を与えてくださった"仮の人"さん( https://twitter.com/kari_math ) への感謝と、他の参加者のクオリティの高い記事の閲覧( https://adventar.org/calendars/7749 ) をしていただけると幸いです。
こういうことをするのははじめてでいろいろ不安なので、不備や質問、アドバイスがありましたら遠慮なくコメントしてください。

概要

この記事では、写像$f:S\rightarrow S$の自身との合成写像を考えて、以下の命題を導く

定義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)$
また、この定理を使いフェルマーの小定理を導くことができる

以下では全体集合を$S$、$f:S\rightarrow S$とする
また、すべての命題に対して詳細な証明を書くとかなり長くなってしまうので、補題の証明はこの記事では略す
$Q$,不安なら補題の証明略すなよ
$A$,建前:読みやすさのほうが重要であると判断したから　本音:めんどくさい
いずれにせよ補題の証明は近いうちにちゃんと記事にするつもりなのでゆるして...
2022/12/23追記:記事にしました( https://mathlog.info/articles/3805 )

証明の流れ

次のような集合を考える
定義1.$m$が正整数のとき、
$cyc_m(f)=${$a$|$f^m(a)=a$かつ$m$未満のすべての正整数$n$について$f^n(a)\neq a$}
とする
このとき、$cyc_m$は位数が$m$の巡回群によく似た性質を持つ
以下では$A_s$と$cyc_m$について2つの事実を証明する
①$p$が素数のとき$A_s(f^p)=A_s(f)\cup cyc_p(f)$かつ$A_s(f)\cap cyc_p(f)=\emptyset$
②$cyc_m(f)$の要素数が有限であるとき、$|cyc_m(f)|$は$m$の倍数である
この2つが成り立つとすると、
$p$が素数、$A_S(f)$,$A_S(f^p)$の要素数が有限のとき、①と包除原理より
$|A_s(f^p)|=|A_s(f)|+|cyc_p(f)|$
②より
$|A_S(f^p)|\equiv |A_S(f)|\hspace{6pt}(mod\hspace{4pt}p)$
となる

$cyc_m(f)$の要素の基本的な性質

定義1:$cyc_m(f)$

定義1.正整数$m$について
$cyc_m(f)=${$\alpha$|$f^m(\alpha)=\alpha$かつ$m$未満のすべての正整数$n$について$f^n(\alpha)\neq \alpha$}
とする
以下では特に言及のない限り$cyc_m(f)$は空集合ではないとし、$\alpha ,\beta\in cyc_m(f),x\in S$とする

定理1,3証明準備

補題0,3

非負整数$a,b$について $f^a(f^b(x))=f^{a+b}(x)$

補題1,1

非負整数$k,l,m$について、$f^m(x)=x\Rightarrow f^{km+l}(x)=f^l(x)$

補題1,2

非負整数$i$について、
$f^i(\alpha)=\alpha\Leftrightarrow i\equiv 0\hspace{6pt}(mod\hspace{4pt}m)$

定理1,3

非負整数$i,j$について、
$f^i(\alpha)=f^j(\alpha)\Leftrightarrow i\equiv j\hspace{6pt}(mod\hspace{4pt}m)$

証明

$\Leftarrow$ $i=am+c,j=bm+c$とおいて補題1,1を適用
$\Rightarrow$ $j\hspace{4pt}mod\hspace{4pt}m=a$として両辺に$f^{m-a}$を作用させると右辺が$\alpha$となるので補題1,2を適用

定理1,4

$f^m(x)=x$かつ、$m$のすべての正の約数$d$(ただし$m$は除く)について$f^d(x)\neq x \Rightarrow x\in cyc_m(f)$

証明

$m=1,2$のとき明らか
$f^n(x)=x$となるような$m$の約数でない、$m$未満の正整数$n$が存在すると仮定する
このような$n$の中で最小のものを$n'$とすると、$m=rn'+s\hspace{4pt}(0< s< n')$となる正整数$r,s$が存在する
このとき$f^m(x)=f^{rn'+s}(x)=f^s(f^{rn'}(x))=f^s(x)=x$となる
$s$が$m$の約数なら$f^d(x)\neq x$と矛盾、$s$が$m$の約数でないなら$n'$が最小であるということと矛盾

定義2:$cyc_m(f,\alpha)$

定義2.正整数$m$と$\alpha\in cyc_m(f)$について
$cyc_m(f,\alpha)=${$f^k(\alpha)$|$k$は非負整数$\hspace{0pt}$}とする

定理2,2証明準備

補題2,1

$cyc_m(f,\alpha)=cyc_m(f,\beta)\Leftrightarrow\beta=f^k(\alpha)$なる非負整数$k$が存在する

定理2,2

すべての$\alpha,\beta$について、
$cyc_m(f,\alpha)=cyc_m(f,\beta)$または$cyc_m(f,\alpha)\cap cyc_m(f,\beta)=\emptyset$

証明

命題$A$について、$A$または$A$でない　は常に真であるので、
$cyc_m(f,\alpha)=cyc_m(f,\beta)$またはすべての非負整数$k$について$\beta\neq f^k(\alpha)$　は真であるから
すべての非負整数$k$について$\beta\neq f^k(\alpha)\Rightarrow{cyc_m(f,\alpha)\cap cyc_m(f,\beta)=\emptyset}$を示せばよい
$x\in cyc_m(f,\alpha)$かつ$x\in cyc_m(f,\beta)$となるような$x$が存在すると仮定すると、
$x=f^k(\alpha)$かつ$x=f^l(\beta)$より$\beta=f^{m+k-l}(\alpha)$となる(後に示すように$k,l$は$m$未満としてよい)

定理2,5証明準備

補題2,3

$cyc_m(f,\alpha)=${$f^k(\alpha)$|$k$は$m$未満の非負整数$\hspace{0pt}$}、特に$|cyc_m(f,\alpha)|=m$である

補題2,4

$f^k(\alpha)\in cyc_m(f)$、特に$cyc_m(f,\alpha)\subset cyc_m(f)$である

定理2,5

$cyc_m(f,\alpha_1,\alpha_2,\cdots,\alpha_n)=\bigcup\limits_{k=1}^n cyc_m(f,\alpha_k)$とすると
$|cyc_m(f,\alpha_1,\alpha_2,\cdots,\alpha_n)|\equiv 0\hspace{4pt}(mod\hspace{4pt}m)$

証明

集合$A$について、$B\subset A$のとき$A\cup B=A$(Bが消える)であるので
$cyc_m(f,\alpha_k)=cyc_m(f,\alpha_i)(1\leqq i< k)$となる$i$が存在するような$cyc_m(f,\alpha_k)$を消せば、
定理2,2、補題2,3と包除原理より
$|cyc_m(f,\alpha_1,\alpha_2,\cdots,\alpha_n)|=m+m+\cdots+m$
$|cyc_m(f,\alpha_1,\alpha_2,\cdots,\alpha_n)|\equiv 0\hspace{4pt}(mod\hspace{4pt}m)$

定理2,6の証明

①$p$が素数のとき$A_s(f^p)=A_s(f)\cup cyc_p(f)$かつ$A_s(f)\cap cyc_p(f)=\emptyset$
①の証明
$x\in A_s(f^p)\Leftrightarrow f^p(x)=x\Leftrightarrow f(x)=x$または$(f^p(x)=x$かつ$f(x)\neq x)$
ここで、$p$の正の約数($p$を除く)は$1$のみなので、定理1,4より
$f^p(x)=x$かつ$f(x)\neq x\Leftrightarrow x\in cyc_p(f)$
また、定義より$f(x)=x\Leftrightarrow x\in A_s(f)$なので
$x\in A_s(f^p)\Leftrightarrow x\in A_s(f)$または$x\in cyc_p(f)$
よって$A_s(f^p)=A_s(f)\cup cyc_p(f)$
$x\in A_s(f)$かつ$x\in cyc_p(f)$なる$x$が存在すると仮定すると、
$f(x)=x$かつ$p$未満のすべての正整数$n$について(特に、$n=1$のときにも)$f^n(x)\neq x$となり矛盾
また$cyc_p(f)$が空集合のときは明らかに$A_s(f)\cap cyc_p(f)=\emptyset$
よって$A_s(f)\cap cyc_p(f)=\emptyset$

②$cyc_m(f)$の要素数が有限であるとき、$|cyc_m(f)|$は$m$の倍数である
②の証明
$cyc_m(f)=${$\alpha_1,\alpha_2,\cdots,\alpha_n$}　のとき、補題2,4より
$cyc_m(f)=cyc_m(f,\alpha_1,\alpha_2,\cdots,\alpha_n)$
定理2,5より$|cyc_m(f)|\equiv 0\hspace{4pt}(mod\hspace{4pt}m)$
また、$cyc_m(f)$が空集合のときも$|cyc_m(f)|=0\equiv 0\hspace{4pt}(mod\hspace{4pt}m)$より②が成り立つことがわかる

①、②が真であることがわかったので、あとは「証明の流れ」と同様にすれば、
定理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)$
がわかる

フェルマーの小定理の証明

$S=\mathbb{C}$、$a$を$2$以上の整数として$f(x)=x^a$として定理2,6を適用すると、$f^p(x)=x^{a^p}$であるので
$|A_\mathbb{C}(x^{a^p})|\equiv |A_\mathbb{C}(x^a)|\hspace{6pt}(mod\hspace{4pt}p)$
またすべての$2$以上の整数$b$について$x^b-x=x(x^{b-1}-1)$で、$x^{b-1}-1=0$は$b-1$個の(相異なる)解を持ち$x=0$が解にならないので、$x^b=x$の(相異なる)解は$b$個ある
よって$|A_\mathbb{C}(x^b)|=b$
これを定理2,6を適用した式に代入することにより、
フェルマーの小定理
$a^p\equiv a\hspace{6pt}(mod\hspace{4pt}p)$
が得られる