您的位置:

欧拉定理证明详解

一、欧拉定理是什么

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