欧拉定理c语言

欧拉定理是指对于任意正整数 a 和 m，若 a 和 m 互质，则有 a^φ(m) ≡ 1 (mod m)，其中 φ(m) 表示欧拉函数，表示小于等于 m 的正整数中与 m 互质的数的个数。

以下是 C 语言实现欧拉定理的代码：

#include <stdio.h>

// 求解 a^b mod m
int mod_pow(int a, int b, int m) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

// 求解欧拉函数的值
int euler(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

int main() {
    int a, m;
    printf("请输入 a 和 m：");
    scanf("%d %d", &a, &m);
    int phi = euler(m);
    int res = mod_pow(a, phi, m);
    printf("%d^%d ≡ %d (mod %d)\n", a, phi, res, m);
    return 0;
}

在该代码中，我们分别实现了求解 a^b mod m 和求解欧拉函数的函数 mod_pow 和 euler，并在主函数中进行了调用。