初等数论

参考资料

\(a \mid b\) \(\Leftrightarrow\) \(a\)整除\(b\) \(\Leftrightarrow\) \(b\)是\(a\)的倍数
算术基本定理（唯一分解定理）: 每个正整数\(n>1\)唯一分解为素因子乘积\(n=\prod p_i^{e_i}\)
\(a \equiv b \pmod{c}\) \(\Leftrightarrow\) \(a=b+kc\)(\(k\)为整数)
模\(m\)算术: 运算数在\(\mathbb{Z}_m\)范围内, 结果取模\(m\), 结果集合为\(\mathbb{Z}_m\)
模指数运算: \((b^a)\%m = (b \cdot (b^{a-1}\%m))\%m\)(可结合快速幂优化)
- 快速幂算法: 二进制展开, \(O(\log a)\), 如pow(base, exp, mod)实现
埃拉托斯特尼筛法: 寻找小于\(n\)的素数, 每遇到素数就标记其倍数为合数
线性筛: \(O(n)\)筛素数, 每个合数标记一次, 维护最小素因子
素数定理: 小于\(n\)的素数个数\(\pi(n) \sim \frac{n}{\ln n}\)
无穷多素数定理: 存在无穷多个素数（欧几里得证明: 假设有限则\(NP+1\)有新素因子）
威尔逊定理: 若\(p\)为素数, 则\((p-1)! \equiv -1 \pmod{p}\)
欧拉定理: 若\(\gcd(a, n)=1\), 则\(a^{\phi(n)} \equiv 1 \pmod{n}\)（费马小定理特例: \(n=p\)素数）
欧拉函数\(\phi(n)\): 小于\(n\)的正整数中与\(n\)互质的数的个数, \(\phi(n)=n\prod_{p|n}(1-1/p)\)
莫比乌斯函数\(\mu(n)\): 若\(n\)有\(k\)不同素因子, \(\mu(n)=(-1)^k\)(平方因子则\(0\)), \(\phi(n)=\sum_{d|n}\mu(d)\frac{n}{d}\)

同余方程\(ax \equiv b \pmod{m}\):
- 令\(d=\gcd(a,m)\), 若\(d\nmid b\)无解; 否则\(d\)个解, 通解\(x=x_0 + \frac{m}{d}t\)
- 若\(d=1\), 存在唯一逆元\(a'\)使得\(aa' \equiv 1 \pmod{m}\)
- \(a'\)通过扩展欧几里得算法求得: \(x \pmod{m}\)
中国剩余定理(CRT):
- 对于方程组\(x \equiv b_i \pmod{m_i}\)(\(m_i\)两两互质)
- 存在唯一解\(x \equiv \sum b_i M_i M_i' \pmod{\prod m_i}\)
- (其中\(M_i = \prod_{j\neq i} m_j\), \(M_i'\)为\(M_i\)模\(m_i\)的逆元)
- 其意义在于将以大数分解为互质的因数, 任意小于大数的数都可以唯一表示为对于每个因数的模的余数的线性组合 (就是 b1-bn) 因此可以分开计算, 最后再将结果合并复原
费马小定理: 若\(p\)为素数且\(p \nmid a\), 则\(a^{p-1} \equiv 1 \pmod{p}\)
Miller-Rabin素性测试: 概率测试, 选底\(a\), 检查\(a^{n-1}\equiv1\pmod{n}\)及中间条件, 多底降低伪素数概率

二次剩余: 若存在\(x\)使\(x^2 \equiv a \pmod{p}\)(\(p\)奇素数, \(p\nmid a\)), 则\(a\)为二次剩余
欧拉判别准则: \(\left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p}\)(\(\equiv1\)剩余, \(\equiv-1\)非剩余)
高斯二次互反律: \(\left( \frac{p}{q} \right)\left( \frac{q}{p} \right) \equiv (-1)^{(p-1)(q-1)/4} \pmod{pq}\)

设\(p\)为素数, \(r\)与\(p\)互质, 最小的\(k\)使得\(r^k \equiv 1 \pmod{p}\)称为\(r\)的阶
若\(r\)的阶等于\(\phi(p)=p-1\), 则称\(r\)为\(p\)的原根
原根判断: 分解\(p-1=q_1^{e_1}\cdots q_t^{e_t}\), 检查\(r^{(p-1)/q_i} \not\equiv1\pmod{p}\)对所有\(i\)
离散对数: 若\(g^e \equiv a \pmod{p}\)(\(g\)原根), 则\(e=\log_g a\)（困难问题）
指数同余: \(a^x \equiv a^y \pmod{p}\) \(\Leftrightarrow x\equiv y \pmod{\ord(a)}\)