数论基础

约数

定义

注：仅讨论正约数。

对于两个数 a、b \in \mathbb{N}，如果存在 ka=b（k \in \mathbb{N}），则称 b 是 a 的倍数，a 是 b 的约数，记作 a \mid b。

如果 a 不是 b 的约数，记作 a \nmid b。

可以发现，对于任意 b，它的约数一定有 1 和 b，这两个数叫做 平凡约数。

特殊的，我们约定 0 是所有非零整数的倍数，即所有非零整数都是 0 的约数。

性质

• 当 d 遍历 b 的所有正约数时，\frac{b}{d} 也遍历 b 的所有正约数。（因为约数成对存在，且乘积为 b）

带余数除法

定义

对于两个数 a、b \in \mathbb{Z}，一定存在唯一的 q、r，使得 b=qa+r，则此时 \frac{b}{a} 的余数为 r，且存在 a \mid b 等价于 a \mid r。

性质

• r 一定处于 0 到 a-1 之间。
• 相邻 a 个数在被 a 除后，r 一定在 0 到 a-1 之间全部出现一遍。

最大公约数和最小公倍数

定义

注：约定 0 和 0 的最大公约数为 0。

如果一个数同时是 a 和 b 的约数，则称它是 a 和 b 的公约数，公约数中最大的数叫做最大公约数，记作 \gcd(a,b)，也可简写为 (a,b)。

如果一个数同时是 a 和 b 的倍数，则称它是 a 和 b 的公倍数，公倍数中最小的数叫做最小公倍数，记作 \operatorname{lcm}(a,b)，也可简写为 [a,b]。

最大公约数和最小公倍数具有许多性质，在此不一一列举。

互质（互素）

若 (a_1,a_2……a_k)=1，则称 a_1,a_2……a_k 互素。

多个互素的数不一定两两互素。

素数和合数

定义

如果一个数的 a 的约数只有平凡约数，则称 a 是素数，否则叫合数。

素数和合数具有许多性质，在此不一一列举。

算术基本定理

算术基本引理

设 p 为素数且 p \mid a_1a_2，则 p \mid a_1 和 p \mid a_2 至少有一个成立。

算术基本定理（唯一分解定理）

设 a \in \mathbb{N}，则必定有：

其中 p_i 均为素数（1 \leq i \leq j）。

标准质因数分解式

将算术基本定理中的相同素数合并，可以得到：

称这个式子为 a 的标准质因数分解式，它可以化为 a = \prod p_i^{k_i}。

算数基本定理和算术基本引理是等价的。

同余

定义

对于 m \neq 0，称 m 为模数（模），若 m \mid (a-b)，则称 a 和 b 模 m 同余，记作 a \equiv b \pmod{m}，此时有 a \bmod m = b \bmod m，即两者余数相同。

性质

同余是线性关系，所以其具有：

• 自反性：a \equiv a \pmod m。
• 对称性：若 a \equiv b \pmod m，则 b \equiv a \pmod m。
• 传递性：若 a \equiv b \pmod m，b \equiv c \pmod m，则 a \equiv c \pmod m。

线性运算，若 a \equiv b \pmod m，c \equiv d \pmod m，则：

• a \pm c \equiv c \pm d \pmod m。
• a \times c \equiv b \times d \pmod m。

乘除性：

• 若 a \equiv b \pmod m，则 ka \equiv kb \pmod {km}。
• 若 a \equiv b \pmod m 且 d \mid a,d \mid b,d \mid m，则 \frac{a}{d} \equiv \frac{b}{d} \pmod {\frac{m}{d}}。
• 若 a \equiv b \pmod m 且 d \nmid m，则 \frac{a}{d} \equiv \frac{b}{d} \pmod m。
• 若 a \equiv b \pmod m、d \mid m，则 a \equiv b \pmod d。

同余类和剩余系（待补）

积性函数

定义

若 f(n) 满足 f(1)=1，且对于任意互质的 x,y \in \mathbb{N}，都存在 f(xy)=f(x)f(y)，则称 f(n) 为积性函数。

若 f(n) 满足 f(1)=1，且对于任意的 x,y \in \mathbb{N}，都存在 f(xy)=f(x)f(y)，则称 f(n) 为完全积性函数。

性质

根据 标准质因数分解式 和 积性函数的定义：

• 若 F(x) 是积性函数，则有 F(x)= F(\prod {p_i}^{k_i}) = \prod F（p_i^{k_i})。
• 若 F(x) 是完全积性函数，则有 F(x) = \prod F(p_i^{k_i})=\prod F(p_i)^{k_i}。

若 f(x) 和 g(x) 均为积性函数，则以下函数也是积性函数：

• h(x)=f(x^p)。
• h(x)=f^p(x)。
• h(x)=f(x)g(x)。
• h(x)=\sum_{d \mid x}f(d)g(\frac{x}{d})。

例子

完全积性函数：单位函数、恒等函数等。

积性函数：欧拉函数、莫比乌斯函数等。

加性函数

定义

若 f(n) 满足 f(1)=0，且对于任意互质的 x,y \in \mathbb{N}，都存在 f(xy)=f(x)+f(y)，则称 f(n) 为加性函数。

若 f(n) 满足 f(1)=0，且对于任意的 x,y \in \mathbb{N}，都存在 f(xy)=f(x)+f(y)，则称 f(n) 为 完全加性函数。

性质

根据 标准质因数分解式 和 加性函数的定义：

• 若 F(x) 是加性函数，则有 F(x) = F(\prod p_i^{k_i}) = \sum F(p_i^{k_i})。
• 若 F(x) 是完全加性函数，则有 F(x) = \sum F(p_i^{k_i}) = \sum F(p_i) \cdot k_i。

素数（待补）

素数的定义，见 素数和合数。

素数判定

由于 约数的性质，如果一个数 a 有约数，则在 1 \sim \sqrt{a} 中，一定有一个数是 a 的约数。

代码实现：

bool chk(int a){
    for(int i=2;i*i<=a;i++) if(a%i==0) return false;
    return true;
}

素数筛

最大公约数

最大公约数的定义，见 最大公约数和最小公倍数。

C++函数

在 C++14 之后，可以使用 __gcd(a,b) 求出 a、b 的最大公约数，竞赛可以使用，但不保证函数本身安全性。

欧几里得算法

已知 a、b 两个数，设 a>b，根据 约数的定义，可以知道，若 b=0，则 \gcd(a,b)=a。

同时，我们知道 \gcd(a,b) = \gcd(b, a \bmod b)，这个等式可以不断缩小 a、b，其证明过程请自行百度。

所以我们可以不断进行 \gcd，直到 b=0，然后返回 a。

代码实现：

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

最小公倍数

最小公倍数的定义，见 最大公约数和最小公倍数。

欧几里得算法

通过短除法，可以得到：

所以，只需要求出最大公约数，就可以求出最小公倍数了。

扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD）常用于求出 ax+by = \gcd(a,b) 的一组可行解。

证明

根据欧几里得算法可知：\gcd(a,b) = \gcd (b,a \bmod b)。

我们设 ax_1+by_1 = gcd(a,b)，bx_2+ (a \bmod b)y_2 = gcd(b,a \bmod b)。

所以 ax_1+by_1 = bx_2+(a \bmod b)y_2。

又因为 a \bmod b = a - \lfloor \frac{a}{b} \rfloor \times b。（自己手模即可发现）

所以

同项的数一定相等，有 x_1=y_2,y_1=x_2 - \lfloor \frac{a}{b} \rfloor \times y_2。

我们可以使用 \gcd(a,b) 不断递归，直到 b=0，此时设置 x=1,y=0，回溯后按照上述等式不停计算。

代码实现

void exgcd(int a,int b){
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
}

基本应用

扩展欧几里得算法可以用来求解 乘法逆元 和线性同余方程。

欧拉函数

定义

欧拉函数，即 \varphi(n)，指的是小于等于 n 的并且和 n 互质的数的个数，例如 \varphi(1)=1。

如果 n 是质数，明显有 \varphi(n)=n-1。

性质

• 欧拉函数是积性函数。

  当 \gcd(a,b) = 1 时，有 \varphi(ab) = \varphi(a) \varphi(b)。
  特别的，因为 \varphi(2)=1，所以 n 是奇数时，有 \varphi(2n)=\varphi(n)。

• n=\sum_{d \mid n} \varphi(d)。

  证明由莫比乌斯反演得，超纲了不写。

• 由定义得，若 n=p^k，其中 p 为质数，则 \varphi(n)=p^k - p^{k-1}。

• 由 标准质因数分解式，设 n=\prod_{i=1}^j p_i^{k_i}，则有 \varphi(n)=n \times \prod_{i=1}^j \frac{p_i-1}{p_i}。

• 由上条性质得，对于任意不全为 0 的整数 m,n，\varphi(mn) \varphi(\gcd(m,n)) = \varphi(m) \varphi(n) \gcd(m,n)。

求单个欧拉函数

由第四条性质可以写出如下代码：

int phi(int n){
    int ans=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){//如果 i 是 n 的一个质因子
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

求多个欧拉函数（欧拉筛）

当我们需要求 \varphi(n) 的时候，根据 欧拉函数的性质，可知：

n 是质数时，\varphi(n)=n-1。

n 是合数时，可以把 n 化为它的最小质因子 a 和另一个数 b 的乘积，此时进行分类讨论：

• 如果 a \mid b，那么 \varphi(n)=\varphi(a \times b)=a \times b \times \prod_{i=1}^j \frac{p_i-1}{p_i}=a \times \varphi(b)。
• 否则有 \gcd(a,b)=1，所以 \varphi(n) = \varphi(a) \varphi(b)。

可以发现，欧拉函数的值和素数有很大关系。事实上，我们可以对素数筛进行修改，从而得到欧拉筛。

代码如下：

int phi[MN],prime[MN];
vector<int> pri;//存储所有质数
//此处的prime true代表合数 false代表素数

void sieve(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!prime[i]){//如果i是素数
            pri.push_back(i);
            phi[i]=i-1;
        }
        for(int j=0;j<pri.size();j++){
            int tmp=pri[j];//所有的tmp都是素数
            if(i*tmp>n) break;//超过n的不需要统计
            prime[i*tmp]=true;//记录i*tmp是合数
            if(i%tmp==0){//如果tmp|i
                phi[i*tmp]=phi[i] * tmp;
                break;//质数筛特性，只筛到最小质因子
            }
            phi[i*tmp]=phi[i]*phi[tmp];//如果两者互质
        }
    }
}

例题：P2158 [SDOI2008] 仪仗队 - 洛谷

裴蜀定理

定义

设 a,b 是不全为零的整数，对于任意整数 x,y，满足 \gcd(a,b) \mid ax+by，且存在 x,y，使得 ax+by=\gcd(a,b)。

证明请见 裴蜀定理 - OI Wiki。

推广

逆定理

设 a,b 是不全为零的整数，若 d 是 a,b 的公因数，且存在 x,y，使 ax+by=d，则有 d = gcd(a,b)。

特殊的，设 a,b 不全为零，若存在 x,y 使 ax+by=1，则有 a,b 互质。

多个整数

裴蜀定理可以推广到多个整数，设 a_1,a_2……a_n 为不全为零的整数，则存在 x_1,x_2……x_n，使得 a_1x_1+a_2x_2+……a_nx_n=\gcd(a_1,a_2……a_n)。其逆定理也同样成立。

例题：P4549 【模板】裴蜀定理 - 洛谷

费马小定理

定义

若 p 为质数且 \gcd(a,p)=1，则 a^{p-1} \equiv 1 \pmod p，也可写为 a^p \equiv a \pmod p。

证明

设一个序列 A=\{ 1,2,……p-1 \}，则 A 序列中每一项对 p 取模之后得到的数正好为 \{ 1,2,……p-1 \}，即 \prod_{i=1}^{p-1} A_i \bmod p 的值一定。

如果一个系数 a 不是模数 p 的倍数，那么 a 的取值对模运算的结果没有影响，所以有：

即：

因为乘法的运算性质，我们可以将 a 提出来，则：

因为 \prod_{i=1}^{p-1} A_i 中所有数都和 p 互质，所以它和 p 也互质，即 \prod_{i=1}^{p-1} A_i \nmid p，根据 同余的性质，有：

证毕。

基本应用

费马小定理可以求解当 p 是质数的时候的 乘法逆元，也就是求解 ax \equiv 1 \pmod p 中的 x，其值为 a^{p-2}。

其他的不知道了。

欧拉定理

定义

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

欧拉定理的证明和费马小定理相似，只需构造一个和 m 互质的数列，在此不详细证明。

并且可以发现，当 m 是质数时，有 \varphi(m)=m-1，带入直接可得费马小定理。

扩展欧拉定理

定义

证明略复杂，请自行百度。

基本应用

可以用于对大指数进行降幂，将其化为 快速幂 可以运算的大小。

例题：P5091 【模板】扩展欧拉定理 - 洛谷

乘法逆元

定义

如果 ax \equiv 1 \pmod b，则称 x 为 a \bmod b 的逆元，记作 a^{-1}。

可以直接使用 扩展欧几里得算法 求出乘法逆元。

线性求逆元（待补）

线性求 n 个数的逆元

线性同余方程

定义

形如 ax \equiv b \pmod n 的方程叫做线性同余方程，其中 a,b,n 已知，需要求解 x，一般情况下，x 不唯一。

可以直接使用 扩展欧几里得算法 求出 x 的一组解。

例题：P1082 [NOIP 2012 提高组] 同余方程 - 洛谷

这道题是线性同余方程的例题，同时也是 乘法逆元 的例题，事实上，对于 扩展欧几里得算法 来说，两者没有任何区别。

中国剩余定理

定义

中国剩余定理（Chinese Remainder Theorem, CRT）可以求解形如下式的一元线性同余方程组（其中 n_1,n_2……n_k 两两互质）：

例如，有一个未知数 x，只知道 x 除以 3 余 2，除以 5 余 3，除以 7 余 2， 问这个数是多少？

这个问题就可以化为以下形式：

过程

1. 计算所有模数的积 sum。
2. 对于第 i 个方程：
   1. 计算 m_i=\frac{sum}{n_i}。
   2. 计算 m_i 在模 n_i 意义下的 乘法逆元 m_i^{-1}。
   3. 计算 c_i=m_i \times m_i^{-1}。
3. 方程组在模 n 意义下的唯一解为 x = \sum_{i-1}^k a_i \times c_i \pmod n。

代码实现

约定模数为 a 数组，余数为 b 数组。

void exgcd(int a,int b,int &x,int &y){
    if(b==0) {x=1,y=0;return;}
    exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
}

int crt(int k){
    int n=1,ans=0;

    for(int i=1;i<=k;i++) n*=a[i];//计算模数积

    for(int i=1;i<=k;i++){
        int m=n/a[i],x,y;
        exgcd(m,a[i],x,y);
        ans=(ans+b[i]*x*m % n) % n;
    }

    return (ans+n) % n;
}

例题：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷

注意：本题使用 long long 会爆精度，建议使用 __int128 或者使用龟速乘。

阶乘取模

介绍（以下待补）

阶乘的符号为 n!，其意义为 \prod_{i=1}^n i。

威尔逊（Wilson）定理

定义

对于自然数 n>1，当且仅当 n 是素数时，(n-1)! \equiv -1 \pmod n。