专栏文章

数论取模学习笔记

WWilliam_Y1
算法·理论参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minwemj5
此快照首次捕获于
2025/12/02 09:27
3 个月前
此快照最后确认于
2025/12/02 09:27
3 个月前
查看原文
前言：本文是作者在对同学讲解完之后有感而发写下的，有错误望指正。

费马小定理

对于一个质数 pp 及一个任意满足 (a,p)=1(a,p)=1 的 aa，我们有：
ap−1≡1(modp)a^{p-1}\equiv1\pmod p

证明

首先我们关注两个引理。

引理一：模的除法

对于任意 mm，cc 满足 (m,c)=1(m,c)=1，若
a×c≡b×c(modm)a\times c\equiv b\times c\pmod m
则
a≡b(modm)a\equiv b\pmod m
事实上，对于任意的
a×c≡b×c(modk)a\times c\equiv b\times c\pmod k
都有
a≡b(modm/(m,c))a\equiv b\pmod{m / (m,c)}
可以试着证明一下，此处不再赘述。

引理二：完全剩余系

完全剩余系
通俗来讲，模 mm 的完全剩余系就是一个有 mm 个元素的集合，其中任意两个数模 mm 的余数都不相等。
如果 {a0,a1,⋯ ,am−1}\{a_0,a_1,\cdots,a_{m-1}\} 是模 mm 的完全剩余系，那么对于满足 (b,m)=1(b,m)=1 的 bb，{b×a0,b×a1,⋯ ,b×am−1}\{b\times a_0,b\times a_1,\cdots,b\times a_{m-1}\} 也是模 mm 的完全剩余系。
证明：
运用反证法。
假设新的集合不是模 mm 的完全剩余系，那么存在 b×aib\times a_i 与 b×ajb\times a_j 使得：
b×ai≡b×aj(modm)b\times a_i\equiv b\times a_j\pmod m
那么由于引理一，有：
ai≡aj(modm)a_i\equiv a_j\pmod m
那么一开始的集合就也不是模 mm 的完全剩余系，与已知条件矛盾。
所以新集合是模 mm 的完全剩余系。

费马小定理的证明

易得 {0,1,2,⋯ ,p−1}\{0,1,2,\cdots,p-1\} 是一个模 pp 的完全剩余系。
由于 (a,p)=1(a,p)=1，根据引理二，{0,a,2a,⋯ ,(p−1)a}\{0,a,2a,\cdots,(p-1)a\} 也是模 pp 的完全剩余系。
我们把两个集合的所有元素（除了 00）全部乘起来再取余，容易得到：
1×2×⋯×(p−1)≡a×2a×⋯×(p−1)a(modp)1\times2\times\cdots\times(p-1)\equiv a\times2a\times\cdots\times(p-1)a\pmod p
即
(p−1)!≡(p−1)!×ap−1(modp)(p-1)!\equiv(p-1)!\times a^{p-1}\pmod p
由于 pp 是质数，明显 (p−1)!(p-1)! 与 pp 互质。
所以根据引理一，得到
ap−1≡1(modp)a^{p-1}\equiv1\pmod p
得证。

费马小定理的应用

求乘法逆元是数论中一个很重要的板块。具体来讲，就是要求满足 a×b≡1(modm)a\times b\equiv1\pmod m 的 bb，此时一般把 bb 写作 a−1a^{-1}。
那么对于一个质数 pp，对于与它互质的 aa，有：
ap−1≡1(modp)a×ap−2≡1(modp)a^{p-1}\equiv1\pmod p\\ a\times a^{p-2}\equiv1\pmod p
所以：
ap−2≡a−1(modp)a^{p-2}\equiv a^{-1}\pmod p
这样再加上一个快速幂模板，我们就可以 O(log⁡p)O(\log p) 求逆元了。
代码如下。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a, p;

inline ll quick_power(ll a, ll b, ll mod) { // a 的 b 次方对 mod 取模
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    scanf("%lld%lld", &a, &p);
    ll ins = quick_power(a, p - 2, p); // 求逆元
    printf("%lld\n", ins);
}

欧拉定理

对于两个数 a,ma,m，如果 (a,m)=1(a,m)=1，那么：
aφ(m)≡1(modm)a^{\varphi(m)}\equiv1\pmod m
注意：这里的 mm 不需要是质数。
什么是 φ(m)\varphi(m)
欧拉函数 φ(m)\varphi(m) 就是 11 到 mm 中与 mm 互质的个数，特别的，φ(1)=1\varphi(1)=1。
例如：φ(6)=2\varphi(6)=2，因为 (1,6)=1(1,6)=1，(5,6)=1(5,6)=1。
闲话
容易发现，如果 mm 是质数，那么 φ(m)=m−1\varphi(m)=m-1，所以我们说费马小定理是欧拉定理的特殊版本。

证明

不会证 qwq。
此处给一个感性的理解。
在费马小定理中，我们可以想象成有 p−1p-1 个点，我们在 11 和 aa（以下默认要取模）之间连一条有向边，在 aa 和 a2a^2 之间连一条有向边，以此类推，那么乘以 aa 的操作就是通过有向边走到下一个顶点，那么从 11 开始走，经过所有边（p−1p-1 条边）后回到原点，说明定理成立。
在欧拉定理中，由于 (a,m)=1(a,m)=1，不断乘以 aa 后得到的数肯定也与 mm 互质，因此我们可以想象成有 φ(m)\varphi(m) 个点，按照同样的方法连边，从 11 开始走，经过所有边（φ(m)\varphi(m) 条边）后回到原点，说明定理成立。
但是，上述理解其实是有问题的。因为两种定理所构造的图都只有一个环，但是环的大小不一定是 φ(m)\varphi(m)，也有可能是它的约数，这在以后学到“阶”的时候会有提及。
所以才说我不会证明了，大家勿喷 qwq。

应用

首先是求逆元，不再赘述。
还有一个应用就是简化乘方运算：对于 (a,m)=1(a,m)=1，我们有
ab≡abmod  φ(m)(modm)a^b\equiv a^{b \mod \varphi(m)}\pmod m
这样能够简化运算复杂度到 O(log⁡φ(m))O(\log \varphi(m))，当然前提是你会快速幂。

补充：欧拉函数的求法

第一种方法：枚举，时间复杂度 O(m)O(m)，不太行。
下面分析更快的做法。
以 m=30m=30 为例，它有三个质因数 {2,3,5}\{2,3,5\}。
那么：
至少 包含一个质因数的数有 302+303+305\dfrac{30}{2}+\dfrac{30}{3}+\dfrac{30}{5} 个。
至少 包含两个质因数的数有 302×3+302×5+303×5\dfrac{30}{2\times 3}+\dfrac{30}{2\times 5}+\dfrac{30}{3\times 5} 个。
至少 包含三个质因数的数有 302×3×5\dfrac{30}{2\times 3\times 5} 个。
根据容斥原理，有：
φ(30)=30−(302+303+305−302×3−302×5−303×5+302×3×5)=30−15−10−6+5+3+2−1=8\begin{aligned} \varphi(30)&=30-(\dfrac{30}{2}+\dfrac{30}{3}+\dfrac{30}{5}-\dfrac{30}{2\times 3}-\dfrac{30}{2\times 5}-\dfrac{30}{3\times 5}+\dfrac{30}{2\times 3\times 5})\\ &=30-15-10-6+5+3+2-1\\ &=8 \end{aligned}
但同时，我们又有
φ(30)=30−(302+303+305−302×3−302×5−303×5+302×3×5)=30×(1−12−13−15+12×3+12×5+13×5−12×3×5)=30×(1−12)×(1−13)×(1−15)=8\begin{aligned} \varphi(30)&=30-(\dfrac{30}{2}+\dfrac{30}{3}+\dfrac{30}{5}-\dfrac{30}{2\times 3}-\dfrac{30}{2\times 5}-\dfrac{30}{3\times 5}+\dfrac{30}{2\times 3\times 5})\\ &=30\times(1-\dfrac{1}{2}-\dfrac{1}{3}-\dfrac{1}{5}+\dfrac{1}{2\times 3}+\dfrac{1}{2\times 5}+\dfrac{1}{3\times 5}-\dfrac{1}{2\times 3\times 5})\\ &=30\times(1-\dfrac{1}{2})\times(1-\dfrac{1}{3})\times(1-\dfrac{1}{5})\\ &=8 \end{aligned}
自己算一下就清楚了。
容斥原理
集合都学过吧。
容斥原理就是说，如果你想要求 nn 个集合的并集，你可以先把 nn 个集合加起来，再减去任选两个集合的交集，再加上任选三个集合的交集，再……最后得到的答案就是 nn 个集合的并集了。
相当于枚举每次取了几个集合进行交集运算（一个就是它本身），再枚举选取的集合，选了奇数个集合就加到答案里，偶数个就减掉。
具体的话自己看一下，此处不是重点。
推广到 mm（证明看这里，但很难所以感性理解一下就好了），如果它有 kk 个 质因数，分别是 {p1,p2,⋯ ,pk}\{p_1,p_2,\cdots,p_k\}，那么：
φ(m)=m×(1−1p1)×(1−1p2)×⋯×(1−1pk)\varphi(m)=m\times(1-\dfrac{1}{p_1})\times(1-\dfrac{1}{p_2})\times\cdots\times(1-\dfrac{1}{p_k})
那么具体怎么找质因数呢？
我们可以从 22 开始枚举，每次枚举到一个就把 mm 里面的这个因子除干净，保证接下来不会找到非质数因子。
由于大于 m\sqrt{m} 的质因子只有一个，我们最后只要再判定一下 mm 是不是大于 11，是的话就说明还有一个（就是现在的 mm）。
代码如下。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll m;

int main() {
    scanf("%lld", &m);
    ll phi = m; // 欧拉函数
    for (ll i = 2; i <= sqrt(m); i++) {
        if (m % i == 0) {
            phi = phi - phi / i; // 避免浮点数精度误差
            while (m % i == 0) m /= i;
        }
    }
    if (m > 1) phi = phi - phi / m;
    printf("%lld\n", phi);
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...