初等数论

参考资料

• 《离散数学及其应用》- 翻译版，包含"离散数学"和组合数学/初等数论等内容 - 4

模与素数

• $a \mid b$ $\Leftrightarrow$ $a$整除$b$ $\Leftrightarrow$ $b$是$a$的倍数
• $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$(可结合快速幂优化)
• 埃拉托斯特尼筛法: 寻找小于$n$的素数，每遇到素数就标记其倍数为合数
• 素数定理: 小于$n$的素数个数$\sim \frac{n}{\ln n}$
• 欧拉函数$\phi(n)$: 小于$n$的正整数中与$n$互质的数的个数

GCD/LCM

• $\gcd(a,b)$/$lcm(a,b)$ = 所有素因子的最小/最大幂次乘积
• $ab = \gcd(a,b) \cdot lcm(a,b)$
• 欧几里得算法: $a=bq+r \Rightarrow \gcd(a,b)=\gcd(b,r)$
• 贝祖定理: 存在整数$x,y$使得$ax+by=\gcd(a,b)$

同余

• 同余方程$ax \equiv b \pmod{m}$:
• 若$\gcd(a,m)=1$，则存在唯一逆元$a'$使得$aa' \equiv 1 \pmod{m}$
• $a'$可通过扩展欧几里得算法求得
• 中国剩余定理(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}$

伪素数

• 若$a^{n-1} \equiv 1 \pmod{n}$但$n$为合数，称$n$为以$a$为底的伪素数
• 卡米切尔数: 对所有与$n$互质的$a$都满足上述条件的合数

原根

• 设$p$为素数，$r$与$p$互质，最小的$k$使得$r^k \equiv 1 \pmod{p}$称为$r$的阶
• 若$r$的阶等于$\phi(p)=p-1$，则称$r$为$p$的原根
• 离散对数: 若$r^e \equiv a \pmod{p}$，则记$e=\log_r a$

应用

• 散列函数设计
• 伪随机数生成: $X_{n+1} \equiv (aX_n + b) \pmod{m}$(要求$\gcd(a,m)=\gcd(b,m)=1$)
• 校验码(如CRC)