100次浏览 发布时间：2024-11-01 08:07:31
欧拉函数是数论中最常用的函数之一：
比如φ(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，因为余数必须是正数。
由费马小定理可以得到：
以上例子直接应用费马定理的结论即可。
欧拉定理和费马小定理都可以用来判断模运算的余数，这种性质在密码学中有广泛的应用。
