用C语言证明费马定律

费马小定理是数论中的一个经典结果，它并不直接适用于C语言编程来证明，因为它是数学理论而不是算法实现。但是，我们可以借助C语言来演示这个定理的一个应用实例。费马小定理表述为：如果p是一个质数，a是任意整数且a不等于0模p，那么a^(p-1) ≡ 1 (mod p)。

下面是一个简单的C程序示例，用于演示当p为质数时，对于给定的a，a^(p-1)对p取余的结果会得到1：

#include <stdio.h>
#include <stdbool.h>

// 判断是否为质数
bool is_prime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

// 使用费马小定理验证
void fermat_law(int a, int p) {
    long long result = 1;
    for (int i = 0; i < p - 1; i++) {
        result *= a;
        result %= p;
    }
    if (result == 1) {
        printf("Fermat's Little Theorem holds: a^(%d-1) mod %d = 1\n", p, p);
    } else {
        printf("The theorem does not hold for this case.\n");
    }
}

int main() {
    int a = 2, p = 7; // 示例值
    if (is_prime(p)) {
        fermat_law(a, p);
    } else {
        printf("%d is not a prime number.\n", p);
    }
    return 0;
}

在这个例子中，我们首先检查p是否为质数，然后利用循环计算a^(p-1)，并查看结果是否满足费马小定理。运行此程序，如果条件满足，将输出定理成立；反之则说明定理不成立。