数论入门

前言：本文主要是听了洛谷夏令营的网课后做的一些数论笔记,难度大致在提高左右,想获得最好的观看体验,建议您准备好纸笔,手动推一下公式加深印象。

整除

若 $a = bk$,其中 $a, b, k$ 都是整数,则 $b$ 整除 $a$,记做 $b|a$。

也称 $b$ 是 $a$ 的约数（因数）,$a$ 是 $b$ 的倍数

性质：

• $1$ 整除任何数,任何数都整除 $0$

• 若 $a|b, a|c$,则 $a|(b + c), a|(b − c)$
  (证明：$b = b’a,c = c’a$ 然后就随便弄了)

• 若 $a|b$,则对任意整数 $c$,$a|bc$

• 传递性：若 $a|b, b|c$,则 $a|c$

---

质数与合数

若大于 $1$ 的正整数 $p$ 仅有两个因子 $1,p$,则称 $p$ 是一个质数（素数）。

否则,若 $p > 1$,则称 $p$ 是一个合数。

1 不是质数也不是合数

若 $n$ 是一个合数,则 $n$ 至少有 $1$ 个质因子。因此其中最小的质因子一定不大于 $\sqrt{n}$

质数有无穷多个。不大于 $n$ 的质数约有 $\frac{n} {\ln n}$ 个。

唯一分解定理：把正整数 n 写成质数的乘积

（即 $n = p_1 ^ {c_1} p_2^{c_2}p_3^{c_3} \dots p_k ^ {c_k}$,其中 pi 为质数且单调不减）,

这样的表示是唯一的。

---

质因数分解

观察到 $n$ 最多只有 1 个大于 $\sqrt{n}$ 的质因子

直接 $O(\sqrt{n})$ 枚举即可

void factor(int x) {
    int tot = 0;
    for (int i = 2;i * i <= x;++i) {
        if (x % i == 0) fac[++tot] = i;
    }
    if (x != 1) fac[++tot] = x;
    return ;
}

---

带余除法、同余

对于$a,b (a,b \in \mathbb{Z},b > 0)$ ,存在唯一的 $q,r(q,r \in \mathbb{Z})$

满足 $a = bq + r$,其中 $0 \leq r < b$

我们把 $q$ 称为商,$r$ 称为余数

余数可以用 $a \mod b(a % b)$来表示。

若两数 $a,b$ 除以 $c$ 的余数相等,则称 $a,b$ 模 $c$ 同余,记作 $a \equiv b (\mod c)$

性质

$a \equiv b (\mod c)$ 与 $c | (a - b)$ 等价

推论

若 $a \equiv b (\mod c),d | c$ 则 $a \equiv b (\mod d)$

---

最大公约数(Greatest Common Divisor)

设 $a, b$ 是不都为 0 的整数,$c$ 为满足 $c|a$ 且 $c|b$ 的最大整数,则称 $c$ 是 $a, b$ 的最大公约数

记为 $\gcd(a, b)$ 或 $(a, b)$

类似地可以定义多个数的最大公约数

求 GCD 的一般公式：质因数分解

$$
\begin{aligned}
&a = p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}\
&b = p_1^{d_1}p_2^{d_2}\dots p_k^{d_k}\
&(a,b) = p_1^{\min{c_1,d_1}}p_2^{\min{c_2,d_2}} \dots p_k^{\min{c_k,d_k}}
\end{aligned}
$$

性质：

$$
\begin{aligned}
&(a, a) = (0, a) = a \
&\text{if } a|b,\text{then } (a, b) = a \
&(a, b) = (a, a + b) = (a, ka + b) \
&(ka, kb) = k·(a, b) \
&(a, b, c) = ((a, b), c)
\end{aligned}
$$

若 $(a, b) = 1$,则称 $a, b$ 互质（互素）

互质的两个数往往有很好的性质

---

欧几里得算法

又称辗转相除法

迭代求两数 gcd 的做法

由 $(a, b) = (a, ka + b)$ 的性质：$(a, b) = (b, a \mod b)$

时间复杂度 $O(\log \max{a,b})$

如何证明？每次递归 $b$ 的范围缩小一半,也就是说要证明 $a \mod b \leq \frac{a}{2}$

分类讨论一手：
$$
\begin{aligned}
&1.b \leq \frac{a}{2}\
&\Rightarrow a \mod b < b \leq \frac{a}{2}\
&2.a > b > \frac{a}{2} \
&\Rightarrow a \mod b = a - b \leq \frac{a}{2}
\end{aligned}
$$

---

裴蜀定理

设 $(a, b) = d$,则对任意整数 $x, y$,有 $d|(ax + by)$ 成立

特别地,一定存在 $x, y$ 满足 $ax + by = d$

等价的表述：不定方程 $ax + by = c (a,b,c \in \mathbb{Z})$有解的充要条件为 $(a, b)|c$

推论：$a, b$ 互质等价于 $ax + by = 1$ 有解

证明

显然有 $d | a,d | b$

根据之前的引理有 $d | ax,d | by$

故 $d | (ax+by)$

对于第二个结论（以下转自OI Wiki）

若任何一个等于 $0$ , 则 $\gcd(a,b)=a$ . 这时定理显然成立。

若 $a,b$ 不等于 $0$ .

由于 $\gcd(a,b)=\gcd(a,-b)$ ,

不妨设 $a,b$ 都大于 $0$ , $a\geq b,\gcd(a,b)=d$ .

对 $ax+by=d$ , 两边同时除以 $d$ , 可得 $a_1x+b_1y=1$ , 其中 $(a_1,b_1)=1$ .

转证 $a_1x+b_1y=1$ .

我们先回顾一下辗转相除法是怎么做的,由 $\gcd(a, b) \rightarrow \gcd(b,a\mod b) \rightarrow …$ 我们把模出来的数据叫做 $r$ 于是,有

$$ \gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1 $$

把辗转相除法中的运算展开,做成带余数的除法,得

$$
\begin{aligned}
a_1 &= q_1b+r_1 &(0\leq r_1<b_1) \
b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \
r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \
&\cdots \
r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \
r_{n-2} &= q_nr_{n-1}+r_n \
r_{n-1} &= q_{n+1}r_n
\end{aligned}
$$

不妨令辗转相除法在除到互质的时候退出则 $r_n=1$ 所以有（ $q$ 被换成了 $x$ ,为了符合最终形式）

$$ r_{n-2}=x_nr_{n-1}+1 $$

即

$$ 1=r_{n-2}-x_nr_{n-1} $$

由倒数第三个式子 $r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}$ 代入上式,得

$$ 1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3} $$

然后用同样的办法用它上面的等式逐个地消去 $r_{n-2},\cdots,r_1$ ,

可证得 $1=a_1x+b_1y$ . 这样等于是一般式中 $d=1$ 的情况。

---

Exgcd

由裴蜀定理可得,方程 $ax + by = \gcd(a,b)$ 必有一组解。

所以我们考虑如何求出这样的方程的一组解。

证明：

设
$$
\begin{aligned}
&ax_1 + by_1 = \gcd(a,b) \
&bx_2 + (a \mod b)y_2 = \gcd(b,a \mod b)
\end{aligned}
$$

则
$$
\begin{aligned}
&\because \gcd(a,b) = \gcd(b,a \mod b)\
&\therefore ax_1 + by_1 = bx_2 + (a \mod b)y_2 \
&\because (a \mod b ) = a - (\lfloor \frac{a}{b} \rfloor \times b)\
&\therefore ax_1 + by_1 = bx_2 + (a-\lfloor \frac{a}{b} \rfloor \times b) y_2 \
\end{aligned}
$$

展开得
$$
\begin{aligned}
&ax_1 + by_1 = ay_2 + bx_2 - \lfloor \frac{a}{b} \rfloor by_2 = &ay_2 + b(x_2 - \lfloor \frac{a}{b} \rfloor y_2)\
&\because a = a,b = b \
&\therefore x_1 = y_2 , y_1 = x_2 - \lfloor \frac{a}{b} \rfloor y_2
\end{aligned}
$$

所以就可以递归求解了。

代码

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

拓展

考虑形如 $ax + by = c (a,b,c \in \mathbb{Z})$ 的方程的所有解

首先由裴蜀定理得,不定方程 $ax + by = c (a,b,c \in \mathbb{Z})$有解的充要条件为 $(a, b)|c$ 。

先考虑求一组特殊解的情况：首先将 $a,b,c$ 都除以 $\gcd(a,b)$ 得 $a_0x + b_0y = c_0$

此时 $\gcd(a_0,b_0) = 1$,所以我们可以求出 $a_0x + b_0y = 1$ 的一组解 $x_0,y_0$ ,则原方程的一组特解为

$$x_1 = \frac{x_0c}{\gcd(a,b)},y_1 = \frac{y_0c}{\gcd (a,b)}$$

然后我们考虑构造所有解的形式：

设有 $d (d \in \mathbb{Q})$ 那么必有 $a(x_1 + db) + b(y_1 - da) = c$

同时,这组解需要保证 $db,da \in \mathbb{Z}$

令当 $d$ 取到最小可能的正值的 $d_x = db,d_y = da$ ,那么任意解中这两个变量与 $x_1,x_2$ 的偏差一定分别是 $d_x,d_y$ 的倍数。

显然,最小的时候 $d_x = \frac{b}{\gcd (a,b)},d_y = \frac{-a}{\gcd (a,b)}$

所有解就是 $x = x_0 + kd_x,y = y_0 + kd_y (k \in \mathbb{Z})$

---

逆元

若 $ax \equiv 1 (\mod b)$,则称 $x$ 是 $a$ 关于模 $b$ 的逆元,

常记做 $a^{-1}$。

回忆同余的性质。上式等价于 $ax + by = 1$

如何求逆元？等价于解方程 $ax + by = 1$

因此逆元不一定存在：存在的充要条件为 $\gcd (a, b) = 1$

推论：$p$ 是质数,$p$ 不整除 $a$,则 $a$ 模 $p$ 的逆元存在。

结论：在 $[0,b)$ 的范围内,若存在 $a$ 关于 $b$ 的逆元,则它是唯一的。

证明：反证法,若存在 2 个 $a$ 关于 $b$ 的逆元,设其为 $x_1,x_2$,不妨假设 $0 < x_1 < x_2 < b$

也就是说 $ax_1 \equiv ax_2 \equiv 1 (\mod b)$

可以得出 $b | a(x_2 - x_1)$ ,由于 $\gcd(a,b) = 1$,所以 $b | (x_2 - x_1)$

也就是有 $0 \leq (x_2 - x_1) < b$ , 所以不成立。

求逆元

我们刚才说求逆元等价于解方程 $ax + by = 1$,所以直接 exgcd 求解。

int inv(int a,int b) {
    int x,y;
    exgcd(a,b,x,y);
    return x;
}

这样求单个逆元的复杂度是 $O(\log n)$。

如何 $O(n)$ 求 $1\dots n$ 模质数 $p$ 的逆元？

• 方法一：递推

  假设现在要求 $i$ 的逆元

  考虑带余除法,设 $p = iq + r$,则有 $iq + r \equiv 0(\mod p)$

  注意到 $p$ 是质数,因此 $r \not = {0}$,$r$ 的逆元存在

  等式两边乘 $i^{−1}r^{−1}$,得到 $qr^{−1} + i^{−1} \equiv 0(\mod p)$

  因此 $i−1 \equiv −qr^{−1} \equiv -\frac{p}{i}(p \mod i)^{−1}(\mod p)$

  注意这里如果直接算 $-\frac{p}{i}$ 会产生负数,然后 $p -\frac{p}{i} \equiv -\frac{p}{i} (\mod p)$,所以这么算就不会出问题

  代码

  int inv[N];
  
  void prework(int n) {
      inv[1] = 1;
      for (int i = 2;i <= n;++i) {
          inv[i] = (p - p / i) * inv[p % i] % p;
      }
  }

• 方法二：倒推

例题：组合数取模 1

回答 $T$ 次询问

每次询问 $C(n, k) \mod 998244353$(一个质数)

$T ≤ 10^5$, $0 \leq k \leq n \leq 10^7$

分析：$C(n, k) = n!/(k!(n − k)!)$

线性求逆,预处理 $n!$ 以及 $n! ^ {-1}$

$O(1)$ 回答询问

---

线性同余方程

形如 $ax \equiv c(\mod b)$ 的方程,称为线性同余方程。

等价于 $ax + by = c$ 因此有解条件为 $\gcd(a, b)|c$

若 $\gcd(a, b) = 1$,则 $x$ 有唯一解 $x ≡ a^{-1}c(\mod b)$。

否则设 $(a, b) = d, a = a^{\prime}d, b = b^{\prime}d, c = c’d$

那么有 $a’x + b’y = c’$,即 $a’x \equiv c’(\mod b’)$

这里 $(a’, b’) = 1$,因此有 $x ≡ (a’)^{−1}c’(\mod b’)$

综上,任意的线性同余方程总可以判定为无解,或化为 $x \equiv a(\mod m)$ 的形式。

---

中国剩余定理

对于同余方程组 $x \equiv a_i(\mod m_i)(i = 1\dots n)$,

若 $m_i$ 两两互质,则 $x$ 在 $\mod M$ 下有唯一解。这里 $M = m_1m_2\dots m_n$

计算方法

1. 计算所有模数的积 $M$
2. 对于第 $i$ 个方程
   1. 计算 $n_i = \frac{M}{m_i}$
   2. 因为 $\gcd(n_i,m_i) = 1$,所以 $n_i$ 关于 $m_i$ 的逆元 $t_i$ 存在,求出 $t_i$
   3. 计算 $c_i = n_i \times t_i$
3. 方程组的唯一解为 $a = \sum_{i = 1}^k a_ic_i (\mod n)$

代码

int CRT(const int a[],const int m[],int n) {
    int M = 1,ans = 0;
    for (int i = 1;i <= n;++i) M *= m[i];
    for (int i = 1;i <= n;++i) {
        int ni = M / m[i],ti = inv(ni,m[i]);
        ans = (ans + a[i] *  ni * ti) % M;
    }
    return ans;
}

应用

某些计数问题或数论问题给出的模数不是质数

但是对其质因数分解会发现它没有平方因子,也就是该模数是由一些不重复的质数相乘得到。

那么我们可以分别对这些模数进行计算,最后用 CRT 合并答案。

---

Lucas 定理

$$ \binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p $$

---

欧拉函数 $\varphi$

欧拉函数 $\varphi$ (Euler’s totient function)

$\varphi (n)$ 定义为 $[1, n]$ 中与 $n$ 互质的数的个数

例：$\varphi (1) = 1, \varphi (2) = 1, \varphi (6) = 2, \varphi (8) = 4$

若 $p$ 为质数,显然 $\varphi (p) = p - 1$

性质

• 欧拉函数是积性函数

  若 $\gcd (a,b) = 1$, $\varphi(ab) = \varphi(a) \times \varphi(b)$

  证明：

  首先令 $S(n)$ 为 $[1,n]$ 中与 $n$ 互质的数的集合

  任取 $S(a),S(b)$ 中的数 $a_0,b_0$

  考虑一个线性同余方程组

  $$
  \begin{cases}
  \ x \equiv a_0 (\mod a)\
  \ x \equiv b_0 (\mod b)
  \end{cases}
  $$

  则根据中国剩余定理有 $x \equiv c_0(\mod ab)$

  可以证明 $\gcd(c_0,a_0) = \gcd(c_0,b_0) = 1$

  所以 $\gcd(c_0,ab) = 1,c_0 \in S(ab)$

  如果反过来,任取 $S(ab)$ 中一个数 $c_0$,那么设 $a_0 = c_0 \mod a,b_0 = c_0 \mod b$

  这样可以证明有 $a_0 \in S(a),b_0 \in S(b)$

  因此,$|S(ab)| = |S(a)| \times |S(b)|$

  也就是 $\varphi(ab) = \varphi(a) \times \varphi(b)$

• 若 $n = p ^ k$,则有 $\varphi(n) = n(1-\frac{1}{p})$

  证明：设 $x$ 为满足 $\gcd(x,p^k) > 1$ 的整数,此时 $p | x$

  则这样的 $x$ 有$\frac{n}{p}$ 个,所以 $\varphi(n) = n - \frac{n}{p} = n(1-\frac{1}{p})$

• 若 $n$ 所有不同的质因子为 $p_1,p_2 \dots p_n$

  则 $\varphi(n) = n(1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \dots (1 - \frac{1}{p_n})$

  证明：把 $n$ 拆成 $p_i ^{a_i}$ 用上面那个就整完了。

根据这些性质,我们可以通过质因子分解求出 $\varphi(n)$,时间复杂度 $O(\sqrt{n})$

代码

int phi(int x) {
    int ans = x;
    for (int i = 2;i * i <= x;++i) {
        if (x % i == 0) {
            while (x % i == 0) x *= i;
            ret = ret / i * (i - 1);//这里等价于刚才的1 - 1/p
        }
    }
    if (x > 1) ret = ret / x * (x - 1);
    return ret;
}

---

欧拉定理

若 $\gcd(a,n) = 1$, 则 $a ^ {\varphi(n)} \equiv 1(\mod n)$

证明

取 $\varphi(n)$ 个与 $n$ 互质且互不同余的整数构成一个集合 $S = {a_1,a_2\dots a_{\varphi(n)}}$ 又称模 $n$ 的简化剩余系。

考虑集合 $S’ = {pa_1,pa_2,\dots,pa_{\varphi(n)}}$, 显然 $S’$ 也是一个模 $n$ 的简化剩余系

这样如果把每个元素都对 $n$ 取模,则有 $S = S’$

所以可以得 $a_1,a_2\dots a_{\varphi(n)} \equiv pa_1,pa_2,\dots,pa_{\varphi(n)}(\mod n)$

将 $a_1,a_2\dots a_{\varphi(n)}$ 约掉就有 $p ^ {\varphi} \equiv 1 (\mod n)$

应用

利用欧拉定理求逆元

$a \times a^{\varphi(n)-1}\equiv 1(\mod n)$

如果是质数,则有 $a \times a^{n-2} \equiv 1(\mod n)$

快速幂实现。

快速幂缩小指数

例：求 $7 ^ {222} (\mod 10)$

解：

$$
\begin{aligned}
&\because \gcd(7,10) = 1\
&\therefore 7^{\varphi(10)} = 7 ^ 5\equiv 1 (\mod 10)\
&\therefore 7^{222} \equiv 7 ^ {222 \mod 5} = 49 \equiv 9 (\mod 10)
\end{aligned}
$$

当 $\gcd(a,n) > 1$ 时,我们有 $a^{\varphi(p)} \equiv a^{2\varphi(p)} (\mod n)$

推论：当 $b \geq \varphi(n)$ 时,$a ^ b \equiv a ^ {b \mod \varphi(n) + \varphi(n)} (\mod n)$