1. 利用费马定理计算 3^201 mod 11

根据费马小定理，如果 p 是一个质数，a 是不是 p 的倍数的整数，那么 a^(p-1) mod p = 1。

因为 11 是质数且 3 不是 11 的倍数，所以有 3^(10) mod 11 = 1。

因此，我们可以将指数 201 拆分为 10 的倍数和余数：201 = 20*10 + 1。

这样，我们可以将原问题转化为计算 3^(20*10 + 1) mod 11。根据模运算法则，有：

3^(20*10 + 1) mod 11 = (3^10)^20 * 3^1 mod 11

因为 3^10 mod 11 = 1，所以

(3^10)^20 * 3^1 mod 11 = 1^20 * 3^1 mod 11 = 3

因此，3^201 mod 11 = 3。

相关问题

写出C语言程序，完成如下任务：生成一个小于100000的正整数，并利用费马定理判断其是否为素数

费马定理（Fermat's Little Theorem）表明，如果p是一个大于1的质数，a是一个不是p的倍数的整数，则\(a^{p-1} \equiv 1 \mod p\)。我们可以利用这个性质来编写一个简单的C语言程序，判断给定的数字是否为素数。

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

// 判断一个数是否为质数的辅助函数
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num == 2 || num == 3) return true;

    // 费马小定理验证法
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
        // 使用费马定理简化条件，只对非平方因子测试
        int powMod = ((long long)num - 1) / i;
        if (powMod > 1 && powMod % i != 0) {
            int result = powMod % i;
            if (result != 1) {
                return false;
            }
        }
    }

    return true;
}

int main() {
    int number;
    
    printf("请输入一个小于100000的正整数：");
    scanf("%d", &number);

    if (isPrime(number)) {
        printf("%d是质数\n", number);
    } else {
        printf("%d不是质数\n", number);
    }

    return 0;
}

在这个程序中，我们首先定义了一个`isPrime`函数，它会检查输入的数字是否满足费马小定理。然后在主函数里获取用户输入并调用`isPrime`函数判断。如果该数是质数，就输出它是质数，反之则说明它不是质数。

7^(-1) mod 160

首先，我们需要找到160的质因数分解：160 = 2^5 * 5。由于7和160互质，所以7在模160意义下有逆元。根据费马小定理，7^(160-1) ≡ 1 (mod 160)。因此，我们可以将7^(-1) mod 160转化为7^(160-2) mod 160。现在，我们可以使用快速幂算法来计算7^(160-2) mod 160。具体步骤如下：

1. 将指数160-2转化为二进制，得到10111110。
2. 从高位到低位依次处理每一位，用平方乘法计算出7^(2^i) mod 160的值，最后将需要的值相乘即可。
3. 7^2 mod 160 = 49
4. 7^4 mod 160 = (7^2 mod 160)^2 mod 160 = 49^2 mod 160 = 241 mod 160 = 81
5. 7^8 mod 160 = (7^4 mod 160)^2 mod 160 = 81^2 mod 160 = 6561 mod 160 = 1
6. 7^16 mod 160 = (7^8 mod 160)^2 mod 160 = 1^2 mod 160 = 1
7. 7^32 mod 160 = (7^16 mod 160)^2 mod 160 = 1^2 mod 160 = 1
8. 7^64 mod 160 = (7^32 mod 160)^2 mod 160 = 1^2 mod 160 = 1
9. 7^128 mod 160 = (7^64 mod 160)^2 mod 160 = 1^2 mod 160 = 1
10. 7^(160-2) mod 160 = 7^128 * 7^32 * 7^2 mod 160 = 1 * 1 * 49 mod 160 = 49

因此，7^(-1) mod 160 = 49。