费马小定理，欧拉定理

定义

费马小定理是这样的，对于整数，和质数，如果与互质，那么有

欧拉将其上升为

证明

首先, 给定一个小于p的正整数的集合 明显与集合中所有的元素互质

用乘以集合中所有的元素并对取模, 那么我们可以得到集合

明显中所有的元素都小于并且由于不能整除$Y$中所有的元素都不等于并且各个元素都不相等

这说明和的构成相同, 只是元素的顺序不同
所以将两个集合的元素分别相乘

两边约去即可得到

如果两边再同时乘以的话就可以得到后面的

欧拉定理

对任意互素的和,设为小于且与互素的正整数的个数,

则：

二者很像, 欧拉定理没有要求必须是素数, 所以它让来代替了集合的作用, 因为二者的元素都是与(或者说)互素的。
欧拉定理扩展：

证明：

首先，我们知道在到的数中，与互质的一共有个，所以我们把这个数拿出来，放到设出的集合中，即为。

那么接下来，我们可以再设出一个集合为，设中的数为：

即：

下面我们证明两个推理：

1. 这些数中的任意两个都不模同余。
   因为如果有
   (这里假定更大一些)，就有:，
   即能整除。但是与互质，与的最大公因子是，而,因而左式不可能被n整除。
   也就是说这些数中的任意两个都不模同余，个数有种余数。
2. 中的数除的余数都与互质：
   我们知道与互质，则 与互质，
   根据欧几里得：
   
   即：
   则 与（也互质 。
   那么这些数除的余数，都在中，因为这是中与互质的所有数，而余数又小于.
   由上面的性质可知：中的数分别对应中的每个数模同余。

即：

把 替换成的形式可得：

很显然，我们应该移项了，但是在移项之前，我们认为这么多的很烦.

那么就先乘起来：

移项可得：

\

不可能为0，

则：

得证：