一、欧拉定理是什么
欧拉定理(Euler's theorem)是一条数论中的基本定理,它表明如果a和n是正整数,且它们互质,则a的欧拉函数(Euler function)φ(n)满足:a^φ(n) ≡ 1(mod n)。
其中,φ(n)表示小于等于n的正整数中与n互质的数的数量(欧拉函数)。例如,φ(7) = 6,φ(8) = 4,φ(9) = 6。
二、欧拉定理的证明
欧拉定理的证明需要用到一些数学知识,包括费马小定理、唯一分解定理等。下面我们将从多个方面来阐述欧拉定理的证明。
三、费马小定理与欧拉定理
费马小定理是欧拉定理的一个基础:如果p是一个质数,a是不是p的倍数的正整数,则a^(p-1) ≡ 1 (mod p)。
int fastPower(int base, int exponent, int mod) { int ans = 1 % mod; while (exponent) { if (exponent & 1) { ans = (long long) ans * base % mod; } base = (long long) base * base % mod; exponent >>= 1; } return ans; } bool isPrime(int n) { if (n <= 2) { return n == 2; } for (int i = 1; i <= 5; ++i) { int a = rand() % (n - 2) + 2; if (fastPower(a, n - 1, n) != 1) { return false; } } return true; } int main() { int p = 113; // 选一个质数p for (int i = 1; i < p; ++i) { if (!isPrime(i)) { continue; } if (fastPower(i, p - 1, p) != 1) { printf("Oops! a = %d is not p-1's residue\n", i); } } return 0; }
四、唯一分解定理
唯一分解定理指出,任何一个大于1的自然数,都可以分解成多个质因数的积,且这种分解方式唯一。
int main() { int n = 100; vector> factors; // 分解结果 for (int i = 2; i <= n; ++i) { if (n % i == 0) { int cnt = 0; while (n % i == 0) { ++cnt; n /= i; } factors.emplace_back(i, cnt); } } for (auto p: factors) { printf("%d ^ %d\n", p.first, p.second); } return 0; }
五、Euler Function
欧拉函数φ(n)表示小于等于n的正整数中和n互质的数的个数。φ(n)可以通过唯一分解定理来计算,假设n = p1^k1 * p2^k2 * p3^k3 * ... * pm^km,则:φ(n) = (p1-1)*p1^(k1-1) * (p2-1)*p2^(k2-1) * ... * (pm-1)*pm^(km-1)。
int eulerPhi(int n) { int ans = n; for (int i = 2; i * i <= n; ++i) { if (n % i) { continue; } while (n % i == 0) { n /= i; } ans = ans / i * (i - 1); } if (n > 1) { ans = ans / n * (n - 1); } return ans; } int main() { int n = 10; // 求10的欧拉函数 printf("%d\n", eulerPhi(n)); return 0; }
六、欧拉定理的证明过程
1. 特殊情况
当n=1时,φ(1)=1,因此a^φ(1)=1,原式成立。
当a=1时,a^φ(n)=1^φ(n)=1,原式成立。
2. 通用情况
设gcd(a,n)=1,将n分解质因数,有n = p1^k1 * p2^k2 * ... * pm^km。根据互质的定义,a^φ(n)与n没有公共质因数,因此a^φ(n) mod pi^ki = 1 mod pi^ki(1≤i≤m)。
因此,只需对每个pi^ki证明即可。设n=pi^ki,则φ(n)=pi^(ki-1) * (pi-1),原式可写成a^(pi^(ki-1) * (pi-1) * s) ≡ 1(mod pi^ki),其中s={p1^(k1-1) * (p1-1) * p2^(k2-1) * (p2-1) * ... * pm^(km-1) * (pm-1)}/pi^(ki-1)
2.1. 当pi为奇素数时
由费马小定理可得,a^(pi-1) ≡ 1(mod pi),故:
a^(pi^(ki-1) * (pi-1) * s) ≡ (a^((pi-1)*s))^(pi^(ki-1)) ≡ 1^(pi^(ki-1)) ≡ 1(mod pi^ki)
2.2. 当pi=2时
当k=1时,φ(2)=1,故a^φ(2)=1,原式成立。
当k>=2时,n=2^k,φ(n)=2^(k-1),因此:
a^(2^(k-1) * s) ≡ (a^(2^(k-2) * s))^2 ≡ ... ≡ ((a^s)^2)^2 ≡ ... ≡ 1(mod 2^k)
3. 证明完毕
综上所述,对于任意的正整数a、n,若gcd(a,n) = 1,则有:a^φ(n) ≡ 1(mod n),即欧拉定理成立。
七、完整代码示例
#include <bits/stdc++.h> using namespace std; int fastPower(int base, int exponent, int mod) { int ans = 1 % mod; while (exponent) { if (exponent & 1) { ans = (long long) ans * base % mod; } base = (long long) base * base % mod; exponent >>= 1; } return ans; } bool isPrime(int n) { if (n <= 2) { return n == 2; } for (int i = 1; i <= 5; ++i) { int a = rand() % (n - 2) + 2; if (fastPower(a, n - 1, n) != 1) { return false; } } return true; } int eulerPhi(int n) { int ans = n; for (int i = 2; i * i <= n; ++i) { if (n % i) { continue; } while (n % i == 0) { n /= i; } ans = ans / i * (i - 1); } if (n > 1) { ans = ans / n * (n - 1); } return ans; } int main() { srand(time(nullptr)); int p = 113; // 选一个质数p for (int i = 1; i < p; ++i) { if (!isPrime(i)) { continue; } if (fastPower(i, p - 1, p) != 1) { printf("Oops! a = %d is not p-1's residue\n", i); } } int n = 10; // 求10的欧拉函数 printf("%d\n", eulerPhi(n)); return 0; }