歐拉定理證明詳解

一、歐拉定理是什麼

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