6

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

437
0

まえがき

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

概要

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

定義0,1
f:SSn回合成した写像をfn(x)とする
(f0(x)=x,f1(x)=f(x),fn+1(x)=f(fn(x)))

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

定理2,6
すべての集合Sと写像f:SSについて、
pが素数、AS(f),AS(fp)の要素数が有限のとき、
有限集合Tの要素数を|T|と表すことにすると、
|AS(fp)||AS(f)|(modp)
また、この定理を使いフェルマーの小定理を導くことができる

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

証明の流れ

次のような集合を考える
定義1.mが正整数のとき、
cycm(f)={a|fm(a)=aかつm未満のすべての正整数nについてfn(a)a}
とする
このとき、cycmは位数がmの巡回群によく似た性質を持つ
以下ではAscycmについて2つの事実を証明する
pが素数のときAs(fp)=As(f)cycp(f)かつAs(f)cycp(f)=
cycm(f)の要素数が有限であるとき、|cycm(f)|mの倍数である
この2つが成り立つとすると、
pが素数、AS(f),AS(fp)の要素数が有限のとき、①と包除原理より
|As(fp)|=|As(f)|+|cycp(f)|
②より
|AS(fp)||AS(f)|(modp)
となる

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

定義1:cycm(f)

定義1.正整数mについて
cycm(f)={α|fm(α)=αかつm未満のすべての正整数nについてfn(α)α}
とする
以下では特に言及のない限りcycm(f)は空集合ではないとし、α,βcycm(f),xSとする

定理1,3証明準備

補題0,3

非負整数a,bについて fa(fb(x))=fa+b(x)

補題1,1

非負整数k,l,mについて、fm(x)=xfkm+l(x)=fl(x)

補題1,2

非負整数iについて、
fi(α)=αi0(modm)

定理1,3

非負整数i,jについて、
fi(α)=fj(α)ij(modm)

証明

i=am+c,j=bm+cとおいて補題1,1を適用
jmodm=aとして両辺にfmaを作用させると右辺がαとなるので補題1,2を適用

定理1,4

fm(x)=xかつ、mのすべての正の約数d(ただしmは除く)についてfd(x)xxcycm(f)

証明

m=1,2のとき明らか
fn(x)=xとなるようなmの約数でない、m未満の正整数nが存在すると仮定する
このようなnの中で最小のものをnとすると、m=rn+s(0<s<n)となる正整数r,sが存在する
このときfm(x)=frn+s(x)=fs(frn(x))=fs(x)=xとなる
smの約数ならfd(x)xと矛盾、smの約数でないならnが最小であるということと矛盾

定義2:cycm(f,α)

定義2.正整数mαcycm(f)について
cycm(f,α)={fk(α)|kは非負整数}とする

定理2,2証明準備

補題2,1

cycm(f,α)=cycm(f,β)β=fk(α)なる非負整数kが存在する

定理2,2

すべてのα,βについて、
cycm(f,α)=cycm(f,β)またはcycm(f,α)cycm(f,β)=

証明

命題Aについて、AまたはAでない は常に真であるので、
cycm(f,α)=cycm(f,β)またはすべての非負整数kについてβfk(α) は真であるから
すべての非負整数kについてβfk(α)cycm(f,α)cycm(f,β)=を示せばよい
xcycm(f,α)かつxcycm(f,β)となるようなxが存在すると仮定すると、
x=fk(α)かつx=fl(β)よりβ=fm+kl(α)となる(後に示すようにk,lm未満としてよい)

定理2,5証明準備

補題2,3

cycm(f,α)={fk(α)|km未満の非負整数}、特に|cycm(f,α)|=mである

補題2,4

fk(α)cycm(f)、特にcycm(f,α)cycm(f)である

定理2,5

cycm(f,α1,α2,,αn)=k=1ncycm(f,αk)とすると
|cycm(f,α1,α2,,αn)|0(modm)

証明

集合Aについて、BAのときAB=A(Bが消える)であるので
cycm(f,αk)=cycm(f,αi)(1i<k)となるiが存在するようなcycm(f,αk)を消せば、
定理2,2、補題2,3と包除原理より
|cycm(f,α1,α2,,αn)|=m+m++m
|cycm(f,α1,α2,,αn)|0(modm)

定理2,6の証明

pが素数のときAs(fp)=As(f)cycp(f)かつAs(f)cycp(f)=
①の証明
xAs(fp)fp(x)=xf(x)=xまたは(fp(x)=xかつf(x)x)
ここで、pの正の約数(pを除く)は1のみなので、定理1,4より
fp(x)=xかつf(x)xxcycp(f)
また、定義よりf(x)=xxAs(f)なので
xAs(fp)xAs(f)またはxcycp(f)
よってAs(fp)=As(f)cycp(f)
xAs(f)かつxcycp(f)なるxが存在すると仮定すると、
f(x)=xかつp未満のすべての正整数nについて(特に、n=1のときにも)fn(x)xとなり矛盾
またcycp(f)が空集合のときは明らかにAs(f)cycp(f)=
よってAs(f)cycp(f)=

cycm(f)の要素数が有限であるとき、|cycm(f)|mの倍数である
②の証明
cycm(f)={α1,α2,,αn} のとき、補題2,4より
cycm(f)=cycm(f,α1,α2,,αn)
定理2,5より|cycm(f)|0(modm)
また、cycm(f)が空集合のときも|cycm(f)|=00(modm)より②が成り立つことがわかる

①、②が真であることがわかったので、あとは「証明の流れ」と同様にすれば、
定理2,6
すべての集合Sと写像f:SSについて、
pが素数、AS(f),AS(fp)の要素数が有限のとき、
有限集合Tの要素数を|T|と表すことにすると、
|AS(fp)||AS(f)|(modp)
がわかる

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

S=Ca2以上の整数としてf(x)=xaとして定理2,6を適用すると、fp(x)=xapであるので
|AC(xap)||AC(xa)|(modp)
またすべての2以上の整数bについてxbx=x(xb11)で、xb11=0b1個の(相異なる)解を持ちx=0が解にならないので、xb=xの(相異なる)解はb個ある
よって|AC(xb)|=b
これを定理2,6を適用した式に代入することにより、
フェルマーの小定理
apa(modp)
が得られる

投稿日:2022123
更新日:2023112
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

抹茶屋
抹茶屋
28
2048
数弱 抹茶より麦茶がすき

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. まえがき
  2. 概要
  3. 証明の流れ
  4. cycm(f)の要素の基本的な性質
  5. 定義1:cycm(f)
  6. 定義2:cycm(f,α)
  7. 定理2,6の証明
  8. フェルマーの小定理の証明