01 整除
学习目标
理解 a∣b 的含义,掌握因数、倍数和整除的基本性质,为同余和 gcd 做准备。
1. 从“平均分没有剩余”开始
12 个苹果平均分给 3 个人,每人 4 个,没有剩余,所以 3 能整除 12,记作 3∣12。
a∣b 的正式含义是:存在整数 k,使 b=ak。
例如 6∣24,因为 24=6×4;但 5∤17,因为 17 除以 5 有余数。
2. 因数和倍数
若 a∣b:
- a 是 b 的因数;
- b 是 a 的倍数。
3. 常用性质
若 a∣b 且 a∣c,则 a∣(b+c)、a∣(b−c)。
若 a∣b,则对任意整数 k,都有 a∣bk。
若 a∣b 且 b∣c,则 a∣c。
4. 为什么算法竞赛要学
以后会看到 m∣(a−b)。它等价于 a≡b(modm),这正是同余的定义。
所以知识链的第一步是:
整除 → 同余 → gcd → 逆元
5. 易错点
a∣b 不是除法 a/b,而是“a 整除 b”。
6. 小练习
- 7∣42 吗?
- 6∣35 吗?
- 若 5∣a 且 5∣b,则 5∣(a+b) 吗?
答案
- 是
- 否
- 是
有帮助,赞一个