欧拉定理
定义
证明
欧拉定理的证明与费马小定理的证明类似，需要以下引理。
tips
此引理的证明使用反证法即可。
下证欧拉定理。
欧拉函数
定义
上面所提及的
即为欧拉函数，表示小于m且与m互素的正整数的个数。
其有以下计算公式。
证明
欧拉函数可由由积性函数的性质得出。
证明所需要引理。
引理2 对一切正整数n, 有
实现
给定整数n，求得其欧拉函数的一个实现如下。
代码语言：javascript复制// 求单个整数的欧拉函数
int Euler(int x) {
int ans = x, m = (int)sqrt(x*1.0) 1;
for(int i = 2; i < m; i) if(x%i == 0) {
ans = ans / i * (i-1);
while(x%i == 0) x /= i;
}
if(x > 1) ans = ans / x * (x-1);
return ans;
}
//递推求[1, n]的欧拉函数值phi[i]
void PhiTable(int n, int* phi) {
for(int i = 1; i <= n; i) phi[i] = i;
for(int i = 2; i <= n; i = 2) phi[i] /= 2;
for(int i = 3; i <= n; i = 2) if(phi[i] == i) { //i是质数
for(int j = i; j <= n; j = i) {
phi[j] = phi[j] / i * (i-1); //i是j的一个因子
}
}
}应用
降幂。 如果模不为素数，就不能用前面讲过的费马小定理来降幂了。
此时可以用欧拉定理降幂，降幂公式如下。
补一个推论
若n>= 1，则
例题
上帝与集合的正确用法 HYSBZ - 3884
Super A^B mod C FZU - 1759
Calculation HDU - 2837
Colossal Fibonacci Numbers! UVA - 11582
Mathematician QSC HDU - 5895
除此之外，还可以求有关阶，原根，指数相关的问题。有些题目也需要转化为带有欧拉函数的公式。
