フェルマーの小定理
素数関連でとにかく出てきまくる重要な定理
出てきすぎて数論における基本的な内容ですらある
拡張版: オイラーの定理, カーマイケルの定理
フェルマーの最終定理が有名すぎて「小」と名前についてしまっている
英語でも Fermat's little theorem と呼ばれる
証明はライプニッツによって与えられている
$ p\in\mathbb P,\ a\in\Zとすると
$ a^p\overset p\equiv a
特に、$ a\in(\Z/a\Z)^\timesの時、
$ a^{p-1}\overset p\equiv1
補題：$ (x+y)^p\overset p\equiv x^p+y^pが成立
$ (x+y)^p=x^p+\sum_{r=1}^{p-1}\,_pC_rx^ry^{p-r}+y^p
$ \overset p\equiv x^p+y^p
証明1
数学的帰納法により示す
$ a=2の時$ 2^p\overset p\equiv 2が成立
補題に$ x=1,y=1を代入すると
$ (1+1)^p\overset p\equiv 1^p+1
$ a=kのときの成立($ k^p\overset p\equiv k)を仮定すると
補題に$ x=k,y=1を代入すると
$ (k+1)^p\overset p\equiv k^p+1
$ \overset p\equiv k+1$ \because仮定より
以上より任意の$ a\in\Nにおいて
$ a^p\overset p\equiv a
証明2
$ a^p=[1+(a-1)]^p
$ \overset p\equiv1^p+(a-1)^p
$ \overset p\equiv1^p+1^p+(a-2)^p
$ \overset p\equiv\cdots
$ \overset p\equiv a