离散数学基础 · 初等数论
离散数学基础：初等数论
来源：初等数论课件（282 页）。
1. 整除、素数与唯一分解
表示存在整数 使 。整除保持整数线性组合。带余除法将 唯一写成 ，其中 且 。
大于 1 的整数只有 1 和自身两个正因子时为素数。每个大于 1 的整数唯一分解成素数幂的乘积。素数有无穷多个：若只有有限个，所有素数之积加 1 的素因子不在原列表中。
2. 最大公因数与 Bézout 等式
最大公因数取素因子指数的逐项最小值，最小公倍数取最大值。对正整数 ：
若 ，则 ，因为两对数有相同的公因子。重复相除，最后一个非零余数是 gcd。
Bézout：存在整数 使 。由辗转相除逐步回代得到系数。例如
从而 。
互素等价于存在整数线性组合等于 1。因此 且 可推出 ；两个互素数都整除 时，它们的乘积也整除 。
3. 同余与剩余类
表示 。固定模数的同余为等价关系，商集由 个剩余类组成；加减乘及非负整数次幂保持同余。
约去因子 时模数必须相应调整：
只有 时能保持原模数直接约去。
4. 一次同余方程与模逆
有解当且仅当 整除 。有解时先除以 ，得到模 下唯一解；模 下有 个不同解类。
例： 化为 ，故 ，模 6 为 2 与 5。
模 的逆存在当且仅当 。扩展欧几里得求出 ，则 是模逆。例：，故 5 模 7 的逆为 3。
5. 欧拉函数、欧拉定理与费马小定理
统计 1 至 中与 互素的数，。由容斥原理：
例如 。
若 ，则 。证明取一组简化剩余系，乘以 只是置换，所有元素相乘再约去可逆因子。
素数 时 ，得到费马小定理：若 不整除 ，；对任意整数 均有 。
验证某底数不满足费马同余可证明该数为合数；满足该同余本身不能证明是素数。
6. 模运算的应用
求幂的末位就是模 10 计算； 因 ，只剩指数 3，末位为 7。大指数可用逐次平方，每步取模，乘法次数 。
星期计算把天数对 7 取模，逐年增加 1，跨闰日再加 1。将一、二月看作上一年的末两个月，可把闰年的影响集中到年界，再按公历 4 年、100 年、400 年规则计闰日。