浅谈——数论全家桶（一）

chenzefan · 2026-07-24 11:40:04 · 算法·理论

我也不知道写了多久，反正理解了很久。这里仅讲解模板题，虽然也很多。

其实能发好几篇的，但这里直接一次性给出干货。大家好好吸收呀。

写 \LaTeX 写疯了，点赞顶我上去吧。

1 欧拉定理/扩展欧拉定理

我们先来了解一下欧拉函数 \varphi。定义 \varphi(n) 表示 1\sim n 中与 n 互质的数的个数。符号表达，\varphi(n)=\displaystyle\sum_{i=1}^n[\gcd(i,n)=1]。

关于欧拉函数的一些性质。

::::success[性质 1]

若 p 为质数，则 \varphi(p)=p-1。 :::info[证明] 因为除了 p 不与本身互质，其余的 1\sim p-1 均与质数 p 互质。则由定义可得。 ::: :::: ::::success[性质 2] 若 p 为质数且 n=p^c，则 \varphi(n)=(p-1)p^{c-1}。 :::info[证明] 考虑正难则反，因为 n 只有一个质因子 p，所以除了 p 的倍数之外其余数都与 n 互质。所以 \varphi(n)=n-\dfrac{n}{p}=n-\dfrac{p^c}{p}=p^c-p^{c-1}=(p-1)p^{c-1}。 ::: :::: :::::success[性质 3] 欧拉函数 \varphi 为积性函数。即若 \gcd(a,b)=1，则 \varphi(a)\varphi(b)=\varphi(ab)。

温馨提示：证明会用到中国剩余定理，谨慎阅读。 ::::info[证明] 引理：

:::info[证明] 假设 $\gcd(ab,x)=g>1$，则必有质数 $p>1$ 满足 $p\mid g,p\mid ab,p\mid x$。

因为 p\mid ab 且 p 为质数，则 p\mid a 或 p\mid b。所以 p\mid \gcd(a,x) 或 p\mid \gcd(b,x)。

因为 \gcd(a,x)=\gcd(b,x)=1，所以质数 p 不存在。与假设矛盾，故原命题得证。\gcd(ab,x)=1 成立。 ::: 定义集合 S(n)=\{x\mid \gcd(x,n)=1,1\le x\le n\}，表示所有不超过 n 的数且与 n 互质的数的集合。显然 |S(n)|=\varphi(n)。

我们易得 \forall 1\le x \le ab,\gcd(ab,x)=1\Rightarrow \gcd(a,x)=\gcd(b,x)=1。

辗转相除法得 \gcd(a,x\bmod a)=\gcd(b,x\bmod b)=1。

就有 S(ab) 到 \{(x,y)\mid x\in S(a),y\in S(b)\} 的映射：\forall 1\le x \le a,1\le y\le b,\gcd(a,x)=\gcd(b,y)=1。

使用中国剩余定理：存在唯一的 1\le z \le ab 使得 z\equiv x\pmod a,z\equiv y\pmod b。

然后就有 \gcd(a,z)=\gcd(b,z)=1。借助引理得 \gcd(ab,z)=1。所以有 \{(x,y)\mid x\in S(a),y\in S(b)\} 到 S(ab) 的映射。故二者为双射（一一对应）。

所以 \{(x,y)\mid x\in S(a),y\in S(b)\} 和 S(ab) 大小一致。

所以 |S(ab)|=|S(a)||S(b)|，即 \varphi(ab)=\varphi(a)\varphi(b)。

故欧拉函数为积性函数。 :::: ::::: ::::success[性质 4]

对于任意的 n，分解为 n=p_1^{c_1}p_2^{c_2}\cdots p_x^{c_x}，则 \varphi(n)=n\displaystyle\prod_{i=1}^x(1-\dfrac{1}{p_i})。 :::info[证明] 由于欧拉函数为积性函数，所以 \varphi(n)=\varphi(p_1^{c_1})\varphi(p_2^{c_2})\cdots \varphi(p_x^{c_x})。

对于 \varphi(p_i^{c_i})，同样考虑正难则反求解。在 1\sim p_i^{c_i} 中，只有 p_i 的整数倍与 p_i^{c_i} 不互质。那么也就是 p_i,p_i\times2,p_i\times3,\cdots,p_i\times p_i^{c_i-1}，也就是 p_i^{c_i-1} 个。所以 \varphi(p_i^{c_i})=p_i^{c_i}-p_i^{c_i-1}=p_i^{c_i}\times(1-\dfrac{1}{p_i})。

然后代入原式，\varphi(n)=\varphi(p_1^{c_1})\varphi(p_2^{c_2})\cdots \varphi(p_x^{c_x})=p_1^{c_1}(1-\dfrac{1}{p_1})p_2^{c_2}(1-\dfrac{1}{p_2})\cdots p_x^{c_x}(1-\dfrac{1}{p_x})=\displaystyle\prod_{i=1}^x p_i^{c_i}(1-\dfrac{1}{p_i})=n\displaystyle\prod_{i=1}^x(1-\dfrac{1}{p_i})。得到结论。 ::: :::: 你可以利用积性函数在 O(n) 的复杂度内求出 1\sim n 的所有 \varphi 值。类似线性筛。但是有时候不需要这么多，我们只需要 \varphi(n)，就可以利用性质 4 做到 O(\sqrt n)。

然后是欧拉定理。

若 \gcd(a,n)=1，则 a^{\varphi(n)}\equiv 1\pmod n。

::::info[证明] 令 1\sim n 中与 n 互质的 \varphi(n) 个数按顺序排列为 x_1,x_2,\cdots,x_{\varphi(n)}。再令 y_i=ax_i(1\le i \le \varphi(n))。

取 y 中任意两个数相减，即 y_i-y_j=ax_i-ax_j=a(x_i-x_j)。设 x_i-x_j=b，则 y_i-y_j=ab。

显然 |b|=|x_i-x_j|<n，且 \gcd(a,n)=1，所以 ab 不会是 n 的倍数。所以 y_i-y_j 不会是 n 的倍数。所以 y_i 和 y_j 再模 n 意义下不同余。所以 y_i\bmod n 有 \varphi(n) 种余数。

反着辗转相除法得 \gcd(n,y_i\bmod n)=\gcd(y_i,n)=\gcd(ax_i,n)=1。得 n 与 y_i\bmod n 互质。

综上可得 x_i 和 y_i\bmod n 必为映射。所以下式一定成立：

令 X=\displaystyle\prod_{i=1}^{\varphi(n)}x_i，则 X\equiv a^{\varphi(n)}X\pmod n。

移项变成 (a^{\varphi(n)}-1)X\equiv0\pmod n。由于 \gcd(X,n)=1，所以 a^{\varphi(n)}-1\equiv0\pmod n，所以 a^{\varphi(n)}\equiv1\pmod n。

然后欧拉定理就得证了。 :::: 欧拉定理也可以推出费马小定理。这里略。

然后是扩展欧拉定理。特别解决 a 和 n 不互质和 b 过大的情况。

a^b \equiv \begin{cases} a^{b \bmod \varphi(n)} & \gcd(a,n)=1 \\ a^b & \gcd(a,n)\neq 1,\, b<\varphi(n) \\ a^{b \bmod \varphi(n)+\varphi(n)} & \gcd(a,n)\neq 1,\, b\ge \varphi(n) \end{cases} \pmod n

::::info[证明]

• 第一条：

  因为 \gcd(a,n)=1，故根据欧拉定理得 a^{\varphi(n)}\equiv 1\pmod n。

  设 b=p \varphi(n)+q，其中 q=b\bmod \varphi(n)(0\le q < \varphi(n))。则 a^b=a^{p\varphi(n)+q}=(a^{\varphi(n)})^p\cdot a^q\equiv1^p\cdot a^q\equiv a^{b\bmod \varphi(n)}\pmod n。

• 第二条易证。

• 第三条：

  将 n 分解质因数为 n=p_1^{c_1}p_2^{c_2}\cdots p_x^{c_x}，只需对每个 i 证明 a^b \equiv a^{b\bmod \varphi(n)+\varphi(n)}\pmod {p_i^{c_i}} 即可，这可以通过中国剩余定理的性质得到。

  于是对 p_i^{c_i} 进行分类。

  • 若 \gcd(a,p_i^{c_i})=1，由欧拉定理可得 a^{\varphi(p_i^{c_i})}\equiv1，又因为 \varphi(p_i^{c_i})\mid \varphi(n)，故
  • 若 \gcd(a,p_i^{c_i})\not=1，则 p_i\mid a。设 a=kp_i，根据欧拉函数的性质 2 得 \varphi(p_i^{c_i})=p_i^{c_i-1}(p_i-1)，于是 \varphi(p_i^{c_i})\ge c_i。可以通过数学归纳法证明。

  所以 b\ge \varphi(n) \ge \varphi(p_i^{c_i}) \ge c_i。故 p_i^{c_i} 为 a^{b \bmod \varphi(n)+\varphi(n)} 的因数，也是 a^b 的因数。

  所以 a^b\equiv a^{b \bmod \varphi(n)+\varphi(n)} \equiv 0\pmod {p_i^{c_i}}。

  综上 a^b\equiv a^{b \bmod \varphi(n)+\varphi(n)}\pmod n。

扩展欧拉定理得证。 ::::

回归题目，我们发现直接使用扩展欧拉定理即可。注意 b 过大，需要一位一位读入并取模。注意开 long long，然后就做完了。

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,mod;
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod,b>>=1;
    }
    return ans;
}
signed main(){
    scanf("%lld%lld",&a,&mod);a%=mod;
    int m=mod,phi=m;
    for(int i=2;i*i<=m;i++){
        if(m%i!=0) continue;
        phi=phi*(i-1)/i;
        while(m%i==0) m/=i;
    }
    if(m!=1) phi=phi*(m-1)/m;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    bool flag=0;
    while(c>='0'&&c<='9'){
        b=b*10+c-'0';
        if(b>phi) flag=1,b%=phi;
        c=getchar();
    }
    if(flag==0) printf("%lld",qpow(a,b));
    else printf("%lld",qpow(a,b+phi));
    return 0;
}

::::

2 裴蜀定理

裴蜀定理（\text{Bézout}）：

对于一个二元一次不定方程 ax+by=c，如果 c 是\gcd(a,b) 的倍数，那么这个方程一定有整数解。

::::info[证明] 简单证明一下。

设 d=\gcd(a,b)，已知 d\mid c，令 a'=\frac{a}{d},b'=\frac{b}{d},c'=\frac{c}{d}。此时满足 \gcd(a',b')=1。

原同余方程 ax\equiv c\pmod b 两边同时除以 d，等价于：a'x\equiv c'\pmod {b'}。

取 x_1,x_2\in\{0,1,\cdots,b'-1\}，假设