数论-费马小定理 学习笔记

1.定理内容

如果p是一个质数，而整数a不是p的倍数，则有。即：

若 为素数，，则 。

第二种表述形式：对于任意整数 ，有 。

在实际的应用中，我们最多用的是第二种表述形式。

2.证明

设一个质数为 ，我们取一个不为 倍数的数 。

构造一个序列：，这个序列有着这样一个性质：

证明：

又因为每一个 都是独一无二的，且

得证（每一个 都对应了一个 )

设 , 则

证毕。

也可用归纳法证明：

显然 ，假设

因为 对于 成立，在模 意义下 ，那么 ，将 带入得

3.应用

1.求逆元

$a^{p - 1} \equiv 1 \pmod p $ 可推出： ，那么剩下的交给快速幂处理即可。

ans = quick_pow(a, mod-2, mod);

2.降幂

，注意前提条件

​​例：​​​求，令，则快速幂求即可。

​​例：​​​(求，可以先) 求，其中。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 1, ans = 0;
    for (int i = 1; i <= 2019; i++) {
        n = n * 2019 % 100;
    }
    for (int i = 1; i <= 11; i++) {
        int x = 1;
        for (int j = 1; j <= n; j++) {
            x = x * i % 101;
        }
        ans = ans + x;
    }
    printf("%d\n", ans % 101);
    return 0;
}

3.待补充