フェルマーの小定理まわりの何か

完全剰余系

$ m>1,m\in\Zとし$ S\sub\Zを考える

$ S:mを法とする完全剰余系\overset{\mathrm{def}}{\iff}\exists_1s\in S,\forall x\in\Z,s\equiv x\bmod m

$ S:mを法とする既約剰余系

$ \overset{\mathrm{def}}{\iff}(\forall s\in S,\gcd(s,m)=1)\land \forall x(\gcd(x,m)=1\implies\exists_1 s\in S,s\equiv x\bmod m)

既約剰余系（完全被約剰余系）

オイラー関数

$ \phi(m):1,\dots,m-1の中で$ mと互いに素であるものの個数

Thm. オイラーの定理（名前？）

$ \forall m(\in\Z)>1,\forall a\in\Z(\gcd(a,m)=1\implies a^{\phi(m)}\equiv 1\bmod m)

proof.

$ S=\set{x_1,\dots,x_{\phi(m)}}:1,\dots,m-1の中でmと互いに素なすべての数から成る既約剰余系

Thm. フェルマーの小定理

系？

pが素数、$ x\in\Zなら1, 2が成り立つ

1. $ x\not\equiv 0\bmod p\implies x^{p-1}\equiv1\bmod p

2. $ x^p\equiv x\bmod p

（方針うろ覚え）定理$ \forall a,m\in\Z,\gcd(a,m)=1\implies a^{\phi(m)}\equiv1\bmod mを示す

仮定として、mは素数だろう

$ S =\set{x_1\dots x_{\phi(m)}}:mと互いに素なあれを使う

aとmは互いに素なので$ ax_iとmも互いに素

$ \forall ax_i,\exists_1 x_j,ax_i\equiv x_j\bmod m

Sが既約剰余系だから。これはなんでこうなったんだっけ、、、

つまり、$ f(i)=jとするとfは全単射

有限集合だから単射から全射が導かれる

は？

ゆえに$ ax_1\dots ax_{\phi(m)}\equiv x_1\dots x_{\phi(m)}\bmod m

$ \iff a^{\phi(m)} x_1\dots x_{\phi(m)}\equiv x_1\dots x_{\phi(m)}\bmod m

$ \iff a^{\phi(m)}\equiv 1\bmod m\square

proof.

$ 1,\dots p-1はすべて$ pと互いに素なので$ \phi(p)=p-1

Prop.

$ a,b\in\Z,a,b\neq0,\gcd(a,b)=1としたとき以下が成り立つ

1. $ \exists c\in\Z,bc\equiv1\bmod a

proof.

$ \exist x, y\in\Z,ax+by=1が成り立つので$ by\equiv 1\bmod a

yをcに書き換えると示したい式になる

2. $ x,y\in\Z,bx\equiv by\bmod a\implies x\equiv y\bmod a

特に、$ bx\equiv 0\bmod a\implies x\equiv 0\bmod a

proof.

$ b(x-y)=an（合同式の定義）

$ b\nmid aより$ an\mid x-yで$ a\mid x-y

$ x\equiv y\bmod a

3. $ d\in\Z,\gcd(a,d)=1\implies\gcd(a,bd)=1

Thm. （最大公約数の定理？）

$ \gcd(a,b)=d\implies \exist x,y\in\Z,ax+by=d