02 同余
学习目标
理解 a≡b(modm) 的含义,掌握同余的加、减、乘性质,并知道为什么不能随便“约掉”。
1. 从时钟理解“模”
15 点在 12 小时制里相当于 3 点,所以 15≡3(mod12)。
2. 同余的含义
a≡b(modm) 表示 a,b 除以 m 后余数相同。
更正式地说:
a≡b(modm)⟺m∣(a−b)
例如 17≡2(mod5),因为 17−2=15,而 5∣15。
3. 完全剩余系
模 m 时,每个整数都能归到 0,1,…,m−1 中的一个余数类。
所以竞赛里讨论“模 m 的解”时,常只看 0≤x<m。
4. 同余可以做什么
若 a≡b(modm),c≡d(modm),则:
a+c≡b+d(modm)
a−c≡b−d(modm)
ac≡bd(modm)
5. 不能随便除
例如 2×1≡2×4(mod6),但不能直接约掉 2 得到 1≡4(mod6)。
模运算里的“除法”需要额外条件。后面学习乘法逆元后,我们会把“除法”改写成“乘逆元”。
6. 小练习
- 23≡?(mod7)
- 14≡2(mod6) 是否成立?
- 若 a≡4(mod7),则 a2≡?(mod7)
答案
- 2
- 成立
- 2
有帮助,赞一个