欧拉定理的证明与费马小定理的证明类似,需要以下引理。
tips
此引理的证明使用反证法即可。
下证欧拉定理。
上面所提及的
即为欧拉函数,表示小于m且与m互素的正整数的个数。
其有以下计算公式。
欧拉函数可由由积性函数的性质得出。
证明所需要引理。
引理2 对一切正整数n, 有
给定整数n,求得其欧拉函数的一个实现如下。
// 求单个整数的欧拉函数
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,则
Colossal Fibonacci Numbers! UVA - 11582
除此之外,还可以求有关阶,原根,指数相关的问题。有些题目也需要转化为带有欧拉函数的公式。