同余学习笔记

Xecades · 2019-01-30 17:07:24 · 个人记录

摘于百度百科

同余是数论中的重要概念

给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)\div m得到一个整数，那么就称整数a与b对模m同余，记作a\equiv b(\mod m)。

读作a同余于b模m，或读作a与b对模m同余。对模m同余是整数的一个等价关系。

可得

1. 若a\equiv 0(\mod m)，则m|a。

性质

1. 反身性：a\equiv a(\mod m)
2. 对称性：若a\equiv b(\mod m)，则b\equiv a(\mod m)
3. 传递性：若a\equiv b(\mod m)，b\equiv c(\mod m)，则a\equiv c(\mod m)
4. 同余式相加：若a\equiv b(\mod m)，c\equiv d(\mod m)，则a\pm c\equiv b\pm d(\mod m)
5. 同余式相乘：若a\equiv b(\mod m)，c\equiv d(\mod m)，则ac\equiv bd(\mod m)
6. 线性运算：如果a\equiv b(\mod m)，c\equiv d(\mod m)，那么
   • a\pm c\equiv b\pm d(\mod m)
   • ac\equiv bd(\mod m)