数学笔记——不定方程、同余、欧拉函数、逆元、中国剩余定理

介绍了不定方程、同余、欧拉函数、逆元、中国剩余定理的相关知识

不定方程

形如 $ax + by = c$，其中 $a$, $b$, $c$ 是已知数的方程被称为二元一次不定方程。它有解当且仅当 $\gcd(a,b)\mid c$

我们可以通过扩展欧几里得算法求不定方程：

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

同余

这是一个同余式：

$$a \equiv b \pmod p $$

同余式两侧可以加减乘但不能直接除

威尔逊定理

正整数 $p$ 是质数的充要条件为 $(p-1)!\equiv-1\pmod p$

欧拉函数

欧拉函数 $\varphi(n)$ 表示小于 $n$ 的数中与 $n$ 互质的数的个数

特别地 $\varphi(1)=1$

欧拉函数有：

• 积性 如果 $\gcd(a,b)=1$，$\varphi(a \times b)=\varphi(a)\times \varphi(b)$
• 欧拉反演 ???
• 对于质数 $p$，$\varphi(p^k)=p^k-p^{k-1}$ (只有 $p$ , $2p$ 至 $p^{k-1}p$ 共 $p^{k-1}$ 个数与 $p^k$ 不互质)

你设 $n$ 的唯一分解式为 $n=p\_1^{k\_1} p\_2^{k\_2}\ldots p\_s^{k\_s}$，则根据积性算出 $\varphi(n)=\Pi_{i=1}^s \varphi(p_i^{k_i})$，而 $\varphi(p_i^{k_i})$ 是可根据上面第三条推算出的

逆元

同余式可以加减乘但不能直接除，所以我们希望得到一个数 $x^{-1}$ 使得任何数除 $x$ 等价于乘 $x^{-1}$

$x$ 的逆元表示为 $x^{-1}$。逆元满足

$$x\times x^{-1}\equiv 1 \pmod p$$

1. $x$ 在模 $p$ 同余下存在逆元当且仅当 $\gcd(x,p)=1$
2. 在模 $p$ 同余下，$x$ 的逆元若存在则唯一
3. 一个数的逆元的逆元等于它本身
4. 在模质数 $p$ 同余下，$[1,p-1]$中所有整数的逆元互不相同

那怎么求呢

费马小定理

在模 $p$ 同余下，$x$ 的逆元为 $x^{p-2}$

线性求

$inv_i$ 表示 $i$ 的逆元
$$inv_i=-\lfloor \frac{p}{i} \rfloor \times inv_{p \mod i} \pmod p$$

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

用exgcd

由于 $x\times x^{-1}\equiv 1 \pmod p$ 它等价于 $xx^{-1}=kp+1\leftrightarrow xx^{-1}+kp=1$ 其中 $x$、$p$ 是已知量，$x^{-1}$、$k$是未知量，带入exgcd exgcd(x,p,ans,y) 即可

中国剩余定理 CRT

$$\quad \left\{ \begin{matrix} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a_n \pmod {m_n} \end{matrix} \right.$$

保证 $m$ 中数互质

$t_i$ 是 $M_i$ 模下 $m_i$的逆元；$M=\Pi m_i$；$M_i=M \div m_i$

$$x\equiv \sum a_i t_i M_i \pmod M$$

模板题：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪。结合exgcd求逆元：

int inv(int a, int d) {
  int x, y;
  exgcd(a, d, x, y);
  return (d + x % d) % d;
}