欧拉定理证明详解

一、欧拉定理是什么

欧拉定理（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<pair> 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  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  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;
}