1 欧几里得算法

欧几里得算法可以求两个数的最大公约数 \(\gcd(a, b)\)。

不妨设 \(a \geq b, a = kb + r(k \geq 1, 0 \leq r < b)\)。

一方面，设 \(d_1\) 为 \(a, b\) 的一个公约数，则 \[ \begin{aligned} a &= k_ad_1\\ b &= k_bd_1\\ r &= a - kb\\ &= (k_a - kk_b)d_1 \end{aligned} \] 即 \(d_1\) 也是 \(r\) 的约数，\(b, r\) 的公约数。

另一方面，设 \(d_2\) 为 \(b, r\) 的一个公约数，则 \[ \begin{aligned} b &= k'_bd_2\\ r &= k_r'd_2\\ a &= kb + r\\ &= (kk'_b + k_r')d_2 \end{aligned} \] 即 \(d_2\) 也是 \(a\) 的约数，\(a, b\) 的公约数。

所以 \(a, b\) 的公约数集合和 \(b, r\) 的公约数集合相同，于是 \(\gcd(a, b) = \gcd(b, r) = \gcd(b, a \bmod b)\)

递归求解，终止状态为 \(b = 0\)，此时原 \(a, b\) 的公约数集合为 \(a\) 的约数集合。

因为 \(a = kb + r > (k + 1)r\) 所以 \(r < \frac{a}{k + 1} \leq \frac{a}{2}\)，所以每次 \(a\) 最少折半，算法复杂度为 \(O(\log a + \log b)\)。

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

2 裴蜀定理

设 \(a, b\) 是不全为零的整数，则存在整数 \(x, y\) 使得 \(ax + by = \gcd(a, b)\)。

2.1 拓展欧几里得算法

拓展欧几里得算法可以求方程 \(ax + by = g\) 的一组解，其中 \(g = \gcd(a, b)\)。

不妨设 \(a \geq b, a = kb + r(k \geq 1, 0 \leq r < b)\)。

\[ \begin{aligned} g &= ax + by \\ &= (kb + r)x + by \\ &= b(kx + y) + rx\\ &= bx' + ry' \\ \end{aligned} \]

假设我们已经得出方程 \(bx + ry = g\) 的一组解 \(x', y'\)，那么原方程的解可以表示为： \[ \begin{cases} x &= y'\\ y &= x' - ky' \end{cases} \]

可以在欧几里得算法的递归中完成，\(a = g, b = 0\) 时显然 \(x = 1, y = 0\) 是一组解。

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

假设用该算法得出一组特解 \((x_0, y_0)\)，那么通解为 \((x_0 + k\dfrac b g, y_0 - k\dfrac a g)\)。

推论： 方程 \(ax + by = c\) 有解的充分必要条件是 \(\gcd(a, b) \mid c\)。

证明： 充分性由裴蜀定理可得证。

必要性：设 \(\gcd(a, b) = g, a = ug, b = vg\)，则 \(c = g(ux + vy)\)，所以 \(g \mid c\)。\(\square\)

因此，对于方程 \(ax + by = c\)，首先用欧几里得算法求出 \(ax+by=g\) 的一组解 \((x_0, y_0)\)，则

原方程的一组特解为 \((\dfrac cg x_0, \dfrac cg y_0)\)，通解为 \((\dfrac cg x_0 + k\dfrac bg, \dfrac cg y_0 - k \dfrac a g)\)。

2.2 线性同余方程

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

求解线性同余方程可以使用拓展欧几里得算法：

原方程等价于 \(ax - b = cy\)，即 \(ax - cy = b\)。

由 裴蜀定理的推论 得知方程有解当且仅当 \(\gcd(a, c) \mid b\)，此时可以用拓展欧几里得算法求解。

2.3 乘法逆元

若 \(ax \equiv 1 \pmod b\)，则 \(x\) 称为 \(a \bmod b\) 的乘法逆元，简称逆元，记作 \(a^{-1}\)。

求解上述线性方程组即可求出单个整数 \(a\) 的乘法逆元。

2.3.1 线性递推逆元

求 \(1 \dots n \bmod p\) 的乘法逆元。

设 \(p = kn + r\)，则 \[ \begin{aligned} kn + r &\equiv 0 &\pmod p\\ r^{-1}(kn + r) &\equiv 0 &\pmod p\\ r^{-1}kn + 1 &\equiv 0 &\pmod p\\ n^{-1} &\equiv -r^{-1}k &\pmod p \end{aligned} \] 得到线性递推式 \[ n^{-1} \equiv \begin{cases} 1, & n = 1\\ -\lfloor\frac p n \rfloor (p \bmod n)^{-1}, & n > 1 \end{cases} \pmod p \]

3 费马小定理

设 \(p\) 是质数，\(a\) 是任意整数且 \(a \not\equiv 0 \pmod p\)，则 \[ a^{p - 1} \equiv 1 \pmod p \]

引理3.1 若 \(p \mid ab, \gcd(p, a) = 1\)，则 \(p \mid b\)。

证明： 根据 裴蜀定理 方程 \(px + ay = 1\) 有整数解 \((x_0, y_0)\)。

所以，\(b = pbx_0 + aby_0 = p(bx_0 + \frac{ab}{p})\)。

又因为 \(p \mid ab\) 所以 \(p \mid b\)。 \(\square\)

引理3.2 设 \(p\) 是质数，\(a\) 是任意整数且 \(a \not\equiv 0 \pmod p\)，则数 \(a, 2a, 3a, \dots, (p - 1)a \pmod p\) 是 \(1 \dots p - 1\) 的一个排列。

证明： 因为 \(p \nmid a\) 所以 \(ia\) 的值只可能在 \(1\) 和 \(p - 1\) 间，下面证明他们两两不同。

假设 \(1 \leq j, k \leq p - 1, ja \equiv ka \pmod p\)，则 \(p \mid (j - k)a\)。

因为假设 \(p \nmid a\)，所以 \(p \mid (j - k)\) (引理3.1)。

又 \(2 - p \leq j - k\leq p - 2\)，所以 \(j - k = 0\)。

所以数 \(a, 2a, 3a, \dots, (p - 1)a \pmod p\) 两两不同。\(\square\)

证明： 由 引理3.2 \[ \begin{aligned} \prod_{i = 1}^{p - 1} ia \equiv (p - 1)! \pmod p\\ a^{p - 1} (p - 1)! \equiv (p - 1)! \pmod p\\ p \mid \left(a^{p -1} - 1\right)(p - 1)! \end{aligned} \] 因为 \(p \nmid (p-1)!\)，所以 \(p \mid (a^{p - 1} - 1)\) (引理3.1)，即 \(a^{p - 1} \equiv 1 \pmod p\)。\(\square\)

用费马小定理可以求模质数的逆元： \[ \begin{aligned} a \cdot a^{p - 2} &\equiv 1 &\pmod p\\ a^{-1} &\equiv a^{p - 2} &\pmod p \end{aligned} \]

4 中国剩余定理(Chinese Remainder Theorem)

设整数 \(m_1, m_2, \dots, m_n\) 其中 任两数 互质，\(M = \prod_{i = 1}^nm_i, M_i = \frac{M}{m_i}\)，则对任意正整数 \(a_1, a_2, \dots, a_n\)，线性同余方程组 \[ \begin{cases} x &\equiv a_1 \pmod {m_1} \\ x &\equiv a_2 \pmod {m_2} \\ &\vdots \\ x &\equiv a_n \pmod {m_n} \end{cases} \] 在模 \(M\) 意义下有唯一解 \[ x \equiv \sum_{i = 1}^{n} a_iM_iv_i \pmod M \] 其中 \(M_iv_i \equiv 1 \pmod {m_i}\)

证明： 将 \(x\) 代入各同余方程，显然都成立。

另外，假设 \(x_1\) 和 \(x_2\) 都是方程组的解，那么

\[ \forall i \in \{1, 2, \cdots , n\}, x_1 - x_2 \equiv 0 \pmod {m_i} \]

因为 \(m_1, m_2, \ldots, m_n\) 两两互质，所以 \(x_1 - x_2 \equiv 0 \pmod M\)，所以方程组在模 \(M\) 意义下有唯一解。\(\square\)

int n;
std::cin >> n;
std::vector<int> a(n), m(n);
LL p = 1;
for (int i = 0; i < n; i++) {
  std::cin >> m[i] >> a[i];
  p *= m[i];
}
LL ans = 0;
for (int i = 0; i < n; i++) {
  int x, y;
  exgcd(p / m[i] % m[i], m[i], x, y);
  ans = (ans + p / m[i] * a[i] * x) % p;
}
std::cout << (ans + p) % p << "\n";

4.1 拓展中国剩余定理

当 \(m_1, m_2, \dots, m_n\) 不满足两两互质时，中国剩余定理失效（因为 \(v_i\) 可能不存在），可以通过合并同余方程的方式解决。

考虑线性同余方程组 \[ \begin{cases} x &\equiv a_1 &\pmod{m_1}\\ x &\equiv a_2 &\pmod{m_2} \end{cases} \] 由第一个方程得 \(x = a_1 + k_1m_1\)，代入第二个方程，\(a_1 + k_1m_1 \equiv a_2 \pmod{m_2}\)，即 \(k_1m_1 + k_2m_2 = a_2 - a_1\)。

由 裴蜀定理的推论 得知方程有解当且仅当 \(\gcd(m_1, m_2) \mid (a_2 - a_1)\)，此时可以用拓展欧几里得算法求解 \(k_1, k_2\)。

假设求出 \(k_1\) 的通解为 \(k_1 = k_0 + t\dfrac{m_2}{\gcd(m_1, m_2)}\)，则 \(x = a_1 + k_1m_1 = a_1 + k_0m_1 + t\dfrac{m_1m_2}{\gcd(m_1, m_2)}\)，即 \[ x \equiv a_1 + k_0m_1 \pmod{\operatorname{lcm}(m_1, m_2)} \]

这样我们把两个同余方程合并成了一个，重复上述操作即可求出原方程组的解。

5 欧拉函数

欧拉函数 \(\varphi(m)\) 表示在 \(1\) 到 \(m\) 之间与 \(m\) 互素的数的个数。即 \[ \varphi(m) = |\{x | \gcd(x, m) = 1, 1 \leq x \leq m\}| \]

5.1 欧拉函数公式

① 如果 \(p\) 为素数且 \(k \geq 1\) 则 \(\varphi(p^k) = p^k - p^{k - 1}\)。

② 如果 \(\gcd(m, n) = 1\)，则 \(\varphi(mn) = \varphi(m)\varphi(n)\)。

证明：

① 只有 \(p, 2p, 3p, \dots, (p^{k - 1} -1)p, p^k\) 和 \(p^k\) 不互素，所以 \(\varphi(p^k) = p^k - p^{k - 1}\)。

② 设 \[ A = \{a | 1 \leq a \leq mn, \gcd(a, mn) = 1\} \] \[ B = \left\{(b, c) | \begin{aligned} &1 \leq b \leq m,\gcd(b, m) = 1,\\ &1 \leq c \leq n,\gcd(c, n) = 1 \end{aligned} \right\} \] 则 \(|A| = \varphi(mn), |B| = \varphi(m)\varphi(n)\)。

一方面，对于 \(A\) 中的任意元素 \(a\)，因为 \(m, n\) 互质，所以 \(\gcd(a, m) = \gcd(a, n) = 1\)。

所以 \(\gcd(a \bmod m, m) = \gcd(a \bmod n, n) = 1\)。

所以 \((a \bmod m, a \bmod n)\) 一定在集合 \(B\) 中。

假设存在 \(a_1, a_2\) 使得 \((a_1 \bmod m, a_1 \bmod n) = (a_2 \bmod m, a_2 \bmod n)\)，则 \(m \mid (a_1 - a_2), n \mid (a_1 - a_2)\)。

又因为 \(m, n\) 互质，所以 \(mn \mid (a_1 - a_2)\)，而 \(a_1, a_2 < mn\)，所以 \(a_1 = a_2\)。

另一方面，对于 \(B\) 中的任意元素 \((b, c)\)，根据中国剩余定理，在模 \(mn\) 意义下必定存在唯一的 \(x\) 满足

\[ \begin{cases} &x \equiv b \pmod m\\ &x \equiv c \pmod n \end{cases} \]

因为 \(\gcd(x, m) = \gcd(b, m) = 1, \gcd(x, n) = \gcd(c, n) = 1\)，所以 \(\gcd(x, mn) = 1\)，即 \(x\) 在集合 \(A\) 中。

综上我们建立了集合 \(A, B\) 之间的单射，所以 \(|A| = |B|\)，即 \(\varphi(mn) = \varphi(m)\varphi(n)\)。\(\square\)

③ 设整数 \(m\) 可以分解为素数的乘积 \(m = p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}\)（由算数基本定理得知这样的分解存在且唯一，这在后文会给出证明），则 \[ \varphi(m) = m\prod_{i=1}^{r}(1 - \frac{1}{p_i}) \]

证明： 由①②得 \[ \begin{aligned} \varphi(m) &= \prod_{i=1}^r\varphi(p_i^{k_i})\\ &= \prod_{i=1}^rp_i^{k_i}(1 - \frac{1}{p_i})\\ &= m\prod_{i=1}^{r}(1 - \frac{1}{p_i}) \end{aligned} \] \(\square\)

5.2 欧拉定理

如果 \(\gcd(a, m) = 1\)，则 \[ a^{\varphi(m)} \equiv 1 \pmod m \]

类似费马小定理的证明，取在 \(1\) 到 \(m\) 之间与 \(m\) 互素的数分别与 \(a\) 相乘即可。

5.3 拓展欧拉定理

\[ a^b\equiv \begin{cases} a^{b\ \bmod\ \varphi(p)},&\gcd(a,p)=1\\ a^b,&\gcd(a,p)\ne1,b<\varphi(p)\\ a^{b\ \bmod\ \varphi(p)\ +\ \varphi(p)},&\gcd(a,p)\ne1,b\ge\varphi(p) \end{cases} \pmod p \]

证明较复杂，这里不给出。

6 素数

6.1 无穷多素数定理

存在无穷多个素数。

证明： 设当前已找到素数 \(p_1, p_2, \dots, p_r\)，下面证明总可以找到另外的素数。

令 \[ A = p_1p_2\dots p_r + 1 \] 若 \(A\) 本身是素数，则证明已完成，否则存在一个素数 \(q\) 整除 \(A\)。

如果 \(q\) 是 \(p_1p_2\dots p_r\) 中的一个，那么 \(A \equiv 1 \pmod q\)，矛盾，所以 \(q\) 是一个新素数。 \(\square\)

6.2 算术级数的素数狄利克雷定理

设 \(\gcd(a, m) = 1\)，则存在无穷多个素数满足 \[ p \equiv a \pmod m \]

6.3 素数定理

设 \(\pi(x)\) 表示小于 \(x\) 的素数个数，则 \[ \lim_{x \to \infty}\frac{\pi(x)}{x / \ln(x)} = 1 \]

6.4 算数基本定理（唯一分解定理）

设整数 \(n \geq 2\)，则 \(n\) 可以唯一分解成素数的乘积 \[ n = p_1p_2\dots p_r(p_1 \leq p_2 \leq \dots \leq p_r) \]

分解的唯一性并不是显然的，因此有必要对这个定理给出证明。 证明分为下面两个部分。

断言1：\(n\) 可以分解成素数的乘积。

证明： \((1)\) \(n = 2, 3\) 时显然成立。

\((2)\) 假设 \(n \leq N\) 可分解为素数的乘积。 对于 \(N + 1\)，若它已经是素数，则证明完成。

否则 \(N + 1\) 是合数，这说明它可以分解成 \(N + 1 = n_1n_2, 2 \leq n_1, n_2 \leq N\)，由归纳假设，\(n_1, n_2\) 都可以表示成素数的乘积，因此 \(N+1\) 也可以表示成素数的乘积。

由 \((1)(2)\) 归纳得知断言1成立。\(\square\)

断言2：\(n\) 的素数分解是唯一的。

证明： 假设 \(n\) 能分解成两种形式的素数乘积 \[ n = p_1p_2\dots p_r = q_1q_2\dots q_s \] 根据 引理3.1，因为 \(p_1 | q_1q_2\dots q_s\)，所以 \(p_1\) 整除 \(q_1, q_2, \dots, q_s\) 其中的某一个，设为 \(q_k\)。

因为 \(p_1, q_k\) 均为素数，所以 \(p_1 = q_k\)，于是可以将它从等式两边除去。重复上述操作 \(r\) 次，最终只可能剩下等式 \(1 = 1\)，于是 \(r = s, p_i = q_i\)。\(\square\)

6.5 梅森素数和完全数

如果对整数 \(a \geq 2, n \geq 2, a^n-1\) 是素数，则 \(a = 2\) 且 \(n\) 为素数。

形如 \(2^p-1\) 的素数被称为梅森素数。

证明： 当 \(a > 2\) 时，因为 \[ a^n-1 = (a - 1)(a^{n-1}+a^{n-2}+\dots+a^2+a+1) \] 所以 \(a^n-1\) 有约数 \(a - 1\)，是合数。

当 \(n\) 是合数时，设 \(n = mk\)，则 \[ 2^n - 1 = \left(2^{m}\right)^k - 1 = (2^m - 1)(2^{m(k-1)}+2^{m(k-2)}+\dots+2^{m}+1) \] 所以 \(2^n-1\) 有约数 \(2^m - 1\)，是合数。\(\square\)

真因数之和等于本身的正整数称为完全数。（真因数即除了本身以外的因数）

梅森素数和完全数有很大的相关性：

6.4.1 欧几里得完全数公式 如果 \(2^p-1\) 是素数，则 \(2^{p-1}(2^p-1)\) 是完全数。

6.4.2 欧拉完全数定理 如果 \(n\) 是偶完全数，则 \(n = 2^{p-1}(2^p-1)\)，其中\(2^p-1\) 是梅森素数。

至今没有人发现有奇完全数。

6.6 Miller-Rabin 素性测试

6.7 Pollard-Rho 质因数分解

7 二项式系数

7.1 模 p 二项式定理

设 \(p\) 为素数，

① \[ \binom{p}{k} \equiv \begin{cases} 0, & 1 \leq k \leq p - 1\\ 1, & k = 0 \text{ or } k = p \end{cases} \pmod p \] ② 对任意数 \(A, B\)，有 \[ (A + B)^p \equiv A^p + B^p \pmod p \]

证明： ① \(\dbinom{p}{k} = \dfrac{p^{\underline{k}}}{k!}\)

当 \(1 \leq k \leq p - 1\) 时，由于 \(p\) 是质数，分子上的 \(p\) 不会被约去，所以 \(\dbinom{p}{k}\equiv 0 \pmod p\)；

当 \(k = 0\) 或 \(k = p\) 时，\(\binom{p}{k} = 1\)。

② 用二项式定理展开再套用①的公式即得证。\(\square\)

7.2 Lucas 定理

设 \(p\) 为素数， \[ \binom n m \equiv \binom{\lfloor n / p \rfloor}{\lfloor m / p \rfloor} \binom{n \bmod p}{m \bmod p} \pmod p \]

证明： \[ (1 + x)^p = 1 + \binom{p}{1}x + \binom{p}{2}x^2 + \dots + \binom{p}{p}x^p \]

由 模 p 二项式定理 有 \[ \begin{aligned} (1 + x)^p &\equiv 1 + x^p &\pmod p\\ (1 + x)^{p^k} &\equiv (1 + x^p)^{p^{k - 1}} \equiv \dots \equiv 1 + x^{p^k} &\pmod p \end{aligned} \]

设 \[ \begin{cases} n &= \sum_{i \geq 0}a_ip^i\\ m &= \sum_{i \geq 0}b_ip^i \end{cases} \] 则 \[ \begin{aligned} (1 + x)^n = \prod_{i \geq 0} (1 + x)^{a_ip^i} &\equiv \prod_{i \geq 0}(1 + x^{p^i})^{a_i} &\pmod p\\ [x^m](1 + x)^n &\equiv [x^m]\prod_{i \geq 0}(1 + x^{p^i})^{a_i} &\pmod p\\ \binom{n}{m} &\equiv \prod_{i \geq 0} \binom{a_i}{b_i} &\pmod p \end{aligned} \]

\(\square\)

7.3 拓展 Lucas 定理

对于 \(p\) 是合数的情形，Lucas 定理失效，此时可以通过另外的方法求二项式系数对 \(p\) 的模。思路如下：

将 \(p\) 质因数分解为 \(p = \sum_{i = 1}^{r} q_i^{k_i}\)，分别求出 \(\dbinom{n}{m} \bmod q_i^{k_i}\)，然后用中国剩余定理合并。

通常二项式系数的计算式为 \(\dbinom{n}{m} = \dfrac{n!}{m!(n - m)!}\)，需要求出 \(m!(n-m)!\) 的逆元，然而在 \(q_i \mid m!(n - m)!\) 的情况下逆元不存在，需要特殊处理。

设 \(n = q^{r(n)}k(n)\)，其中 \(k \nmid q\)，则 \[ \binom{n}{m} = \frac{n!}{m!(n - m)!} = \frac{n!}{k(m!)k((n-m)!)}\cdot q^{-r(m) - r(n - m)} \] 这样逆元都是存在的，问题在于求 \(r(n!)\)。

太毒瘤了，咕咕咕……

7.4 Kummer 定理

\(\dbinom{n + m}{m}\) 中素因子 \(p\) 的个数等于 \(n, m\) 在 \(p\) 进制下做加法的进位次数。

例题 CF582D

8 二次剩余

直接拖了 yosupo 的板子。

namespace SqrtMod {
using Int = long long;
// a^-1 (mod m)
//   m > 0
Int modInv(Int a, Int m) {
  Int b = m, x = 1, y = 0, t;
  for (; ; ) {
    t = a / b; a -= t * b;
    if (a == 0) {
      assert(b == 1 || b == -1);
      if (b == -1) y = -y;
      return (y < 0) ? (y + m) : y;
    }
    x -= t * y;
    t = b / a; b -= t * a;
    if (b == 0) {
      assert(a == 1 || a == -1);
      if (a == -1) x = -x;
      return (x < 0) ? (x + m) : x;
    }
    y -= t * x;
  }
}
// Jacobi symbol (a/m)
//   m > 0, m: odd
int jacobi(Int a, Int m) {
  int s = 1;
  if (a < 0) a = a % m + m;
  for (; m > 1;) {
    a %= m;
    if (a == 0) return 0;
    const int r = __builtin_ctz(a);
    if ((r & 1) && ((m + 2) & 4)) s = -s;
    a >>= r;
    if (a & m & 2) s = -s;
    std::swap(a, m);
  }
  return s;
}

// sqrt(a) (mod p)
//   p: prime, p < 2^31, -p^2 <= a <= P^2
//   (b + sqrt(b^2 - a))^((p+1)/2) in F_p(sqrt(b^2 - a))
std::vector<Int> sqrtMod(Int a, Int p) {
  static std::mt19937 rnd(1024);
  if (p == 2) return {a & 1};
  const int j = jacobi(a, p);
  if (j == 0) return {0};
  if (j == -1) return {};
  Int b, d;
  for (;;) {
    b = rnd() % p;
    d = (b * b - a) % p;
    if (d < 0) d += p;
    if (jacobi(d, p) == -1) break;
  }
  Int f0 = b, f1 = 1, g0 = 1, g1 = 0, tmp;
  for (Int e = (p + 1) >> 1; e; e >>= 1) {
    if (e & 1) {
      tmp = (g0 * f0 + d * ((g1 * f1) % p)) % p;
      g1 = (g0 * f1 + g1 * f0) % p;
      g0 = tmp;
    }
    tmp = (f0 * f0 + d * ((f1 * f1) % p)) % p;
    f1 = (2 * f0 * f1) % p;
    f0 = tmp;
  }
  if (g0 < p - g0) return {g0, p - g0};
  return {p - g0, g0};
}
} // namespace SqrtMod

9 离散对数

求解同余方程 \(a^x \equiv b \pmod p\)。

9.1 大步小步算法(Baby Step Giant Step)

设 \(\gcd(a, p) = 1\)。

令 \(x = kT - m(T = \lceil \sqrt p \rceil, 0 \leq m < T)\)。

原方程变为 \[a^{kT - m} \equiv b \pmod p\]

由于 \(a, p\) 互质，\(a\) 存在逆元，于是方程等价于 \[(a^T)^{k} \equiv ba^m \pmod p\]

把 \(ba^m\) 的所有值插入哈希表，然后枚举 \(k\) 即可。

复杂度 \(O(\sqrt p)\)。

9.2 EXBSGS

设 \(\gcd(a, p) \neq 1\)。

先验证 \(x = 0\)，下面假定 \(x > 0\)。

设 \(d = \gcd(a, p)\)，当 \(d \nmid b\) 时方程无解。

否则方程等价于 \[a^{x-1}\dfrac{a}{d} \equiv \dfrac{b}{d} \pmod {\dfrac{p}{d}}\]

重复此过程，直到底数和模数互质，此时可以用 BSGS 求解。

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

int bsgs(int a, int b, int p) { // Assume: $0 \leq a, b < p$
  if (b == 1 || p == 1) return 0;
  int d = std::gcd(a, p);
  if (d != 1) {
    if (b % d) return -1;
    p /= d;
    int ans = bsgs(a, 1LL * b / d * inv(a / d, p) % p, p);
    return ~ans ? ans + 1 : ans;
  }
  HashTable::Map mp;
  int t = sqrt(p) + 1, pw = 1;
  for (int i = 0; i < t; i++, pw = 1LL * pw * a % p) {
    mp[1LL * pw * b % p] = i;
  }
  for (int i = 1, a = pw; i <= t; i++, pw = 1LL * pw * a % p) {
    auto it = mp.find(pw);
    if (it != mp.end()) return i * t - it->second;
  }
  return -1;
}

10 阶和原根

下面的内容大部分摘自 OI Wiki。

10.1 阶

阶：由欧拉定理可知，对 \(a\in \mathbf{Z}\)，\(m\in\mathbf{N}^{*}\)，若 \(\gcd(a,m)=1\)，则 \(a^{\varphi(m)}\equiv 1\pmod m\)。

因此满足同余式 \(a^n \equiv 1 \pmod m\) 的最小正整数 \(n\) 存在，这个 \(n\) 称作 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)。

定理 10.1.1：\(a,a^2,\cdots,a^{\delta_m(a)}\) 模 \(m\) 两两不同余。

定理 10.1.2：若 \(a^n \equiv 1 \pmod m\)，则 \(\delta_m(a)\mid n\)。

推论：若 \(a^p\equiv a^q\pmod m\)，则有 \(p\equiv q\pmod{\delta_m(a)}\)。

还有两个与四则运算有关的重要性质。

定理 10.1.3：设 \(m\in\mathbf{N}^{*}\)，\(a,b\in\mathbf{Z}\)，\(\gcd(a,m)=\gcd(b,m)=1\)，则

\[ \delta_m(ab)=\delta_m(a)\delta_m(b) \]

的充分必要条件是

\[ \gcd\big(\delta_m(a),\delta_m(b)\big)=1 \]

证明：

必要性

由 \(a^{\delta_m(a)}\equiv 1 \pmod m\) 及 \(b^{\delta_m(b)} \equiv 1 \pmod m\)，可知

\[ (ab)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))}\equiv 1 \pmod m \]

由前面所述阶的性质，有

\[ \delta_m(ab)\mid\operatorname{lcm}\big(\delta_m(a),\delta_m(b)\big) \]

又由于 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\)，故

\[ \delta_m(a)\delta_m(b)\mid\operatorname{lcm}\big(\delta_m(a),\delta_m(b)\big) \]

即 \(\gcd(\delta_m(a),\delta_m(b))=1\)。

充分性

由 \((ab)^{\delta_m(ab)}\equiv 1 \pmod m\) 可知

\[ 1 \equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)\delta_m(b)} \pmod m \]

故 \(\delta_m(a)\mid\delta_m(ab)\delta_m(b)\)。结合 \(\gcd(\delta_m(a),\delta_m(b))=1\) 即得

\[ \delta_m(a)\mid\delta_m(ab) \]

对称地，同理可得

\[ \delta_m(b)\mid\delta_m(ab) \]

所以

\[ \delta_m(a)\delta_m(b)\mid\delta_m(ab) \]

另一方面，有

\[ (ab)^{\delta_m(a)\delta_m(b)}\equiv(a^{\delta_m(a)})^{\delta_m(b)}\times(b^{\delta_m(b)})^{\delta_m(a)}\equiv 1 \pmod m \]

故

\[ \delta_m(ab)\mid\delta_m(a)\delta_m(b) \]

综合以上两点即得

\[ \delta_m(ab)=\delta_m(a)\delta_m(b) \]

\(\square\)

定理 10.1.4：设 \(k \in \mathbf{N}\)，\(m\in \mathbf{N}^{*}\)，\(a\in\mathbf{Z}\)，\(\gcd(a,m)=1\)，则

\[ \delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd\big(\delta_m(a),k\big)} \]

证明：注意到：

\[ a^{k\delta_m(a^k)}=(a^k)^{\delta_m(a^k)}\equiv 1 \pmod m \]

\[ \Rightarrow \delta_m(a)\mid k\delta_m(a^k) \]

\[ \Rightarrow \dfrac{\delta_m(a)}{\gcd\big(\delta_m(a),k\big)}\mid\delta_m(a^k) \]

另一方面，由 \(a^{\delta_m(a)}\equiv 1 \pmod m\)，可知：

\[ (a^k)^{\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}}=(a^{\delta_m(a)})^{\dfrac{k}{\gcd(\delta_m(a),k)}}\equiv 1 \pmod m \]

故：

\[ \delta_m(a^k)\mid\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]

综合以上两点，得：

\[ \delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]

\(\square\)

10.2 原根

原根：设 \(m \in \mathbf{N}^{*}\)，\(a\in \mathbf{Z}\)。若 \(\gcd(a,m)=1\)，且 \(\delta_m(a)=\varphi(m)\)，则称 \(a\) 为模 \(m\) 的原根。

10.2.1 原根个数

若一个数 \(m\) 有原根，则它原根的个数为 \(\varphi(\varphi(m))\)。

10.2.2 原根存在定理

原根存在定理：一个数 \(m\) 存在原根当且仅当 \(m=2,4,p^{\alpha},2p^{\alpha}\)，其中 \(p\) 为奇素数，\(\alpha\in \mathbf{N}^{*}\)。

10.2.3 求原根

原根判定定理：若一个数 \(g\) 是模 \(m\) 的原根，则有对于 \(\varphi(m)\) 任何大于 \(1\) 且不为自身的因数 \(p\)，都有 \(g^{\varphi(m)/p}\not\equiv 1\pmod m\)。

最小原根的数量级 王元于 \(1959\) 年证明了若 \(m\) 有原根，其最小原根是不多于 \(m^{0.25}\) 级别的。

于是可以从小到大枚举判定。

由 定理 10.1.4 可知，设 \(g\) 为模 \(m\) 的任意原根，\(a = g^x\)，则 \(a\) 为模 \(m\) 的原根当且仅当 \(\gcd(x, \varphi(m)) = 1\)。

所以可以枚举 \(x\) 求出所有 \(\varphi(\varphi(m))\) 个原根。

11 数论函数

11.1 积性函数

若数论函数 \(f\) 满足对于任意的 \(a, b \in \mathbf{N}^*, \gcd(a, b) = 1\) 都有 \(f(ab) = f(a)f(b)\)，则称 \(f\) 为积性函数。

特别地，如果对于任意 \(a, b \in \mathbf{N}^*\) 都满足上面的条件，则称 \(f\) 为完全积性函数。

最后修改于 2021-08-13