欧拉定理是什么（欧拉定理和费马小定理）

欧拉函数是数论中最常用的函数之一：

比如φ(8)=1,3,5,7，也就是与8互素的4个数字。

以上是与欧拉函数有关的两个定理，很好理解。

以上定理是欧拉函数的应用。因为任何整数都可以进行素因子分解，比如72=2^3*3^2，所以有以上结论。

在数论中，欧拉定理（Euler Theorem，也称费马-欧拉定理或欧拉函数定理）是一个关于同余的性质：

以上定理的关键在于方程：

这个方程由上一步得出，方程右边就是1mod(m)。接下来只要对方程左边应用公式：

(a*b)%p=((a%p)*(b%p))%p，就可以得到想要证明的结论。

以上是一个例题。可以看到，欧拉定理可以用于判断很大的数字的除法得出的余数。

与欧拉定理密切相关的就是费马小定理。费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）：

也可以写成：

以下是费马定理的一个应用：

其中的-19x9本来是81x9，因为a mod m = (a-m) mod m。最后-171模100，得出的余数必须加上100，因为余数必须是正数。

由费马小定理可以得到：

以上例子直接应用费马定理的结论即可。

欧拉定理和费马小定理都可以用来判断模运算的余数，这种性质在密码学中有广泛的应用。