欧拉定理及其证明[补档]
一.欧拉定理
背景：首先你要知道什么是欧拉定理以及欧拉函数。
下面给出欧拉定理，对于互质的a,p来说，有如下一条定理
[a^{phi(p)}equiv1(mod;p)
]
这就是欧拉定理
二.剩余系
定义：对于集合({k*m+a|kin mathbb{Z},0<=a<m}),我们将它称之为一个模m的同余类记为(overline{a})
那么很显然的，这样的同余类有m个，他们构成m的完全剩余系。
对于m来说，与m互质的数有(phi(m))个，那么这(phi(m))个数所代表的同余类合称为m的简化剩余系。
三.证明欧拉定理
对于数p来说，他有一个简化剩余系，我们记为(x_1,x_2...x_{phi(p)}),对于任意一个(x_i*a)因为(x_i,a)都与p互质，所以它们的乘积必然在简化剩余系中。
很显然的，对于任意的(x_i,x_j)来说
[a*x_i
ot equiv a*x_j(mod;p)
]
(毕竟左右两边一个质因子都没有呢)
有了上面的条件，我们可以得出这个结论
[x_1*a*x_2*a*...x_{phi(p)}*a为x_1,x_2...x_{phi(p)}的一个排列
]
则
[ecause x_1*x_2*...*x_{phi(p)}equiv x_1*a*x_2*a*...x_{phi(p)}*a\
herefore 1equiv a^{phi(p)}
]
证毕。