同余定理是数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。
同余符号
两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对模m同余或a同余于b模m。记作a≡b(mod m)
【定义】 设m是大于1的正整数，a、b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod m)。显然有如下事实：
- 若a≡0(mod m)，则m|a;
- a≡b(mod m)等价于a与b分别用m去除，余数相同。
证明
充分性：
若a和b用m相除留下相同的余数r，则 a=q1m+r, b=q2m+r,q1和q2为某两个整数，由此的a-b=(q1m+r)-(q2m-r)=m(q1-q2)，根据整除定义，我们有m|(a-b)，由同余式定义得出结论：a≡b(mod m)
同余性质
- 反身性：a≡a (mod m)
- 对称性： 若a≡b(mod m)，则b≡a(mod m)
- 传递性： 若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)
- 同余式相加：若a≡b(mod m)，b≡c(mod m)，则a ± c≡b ± d(mod m)
- 同余式相乘：若a≡b(mod m)，b≡c(mod m)，则ac≡bd(mod m)
- 线性运算：如果a≡b(mod m)，c≡d(mod m)，那么a ± c≡b ± d(mod m)，且
a * c≡b * d(mod m) - 除法：若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数。特殊地 ,gcd(c,m)=1 则a ≡ b (mod m)
- 幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)
- 若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)
- 若a ≡ b (mod mi) (i=1,2…n) 则 a ≡ b (mod [m1,m2,…mn]) 其中[m1,m2,…mn]表示m1,m2,…mn的最小公倍数
相关定理
- 欧拉定理
- 费马小定理
- 中国剩余定理（孙子定理）
转载地址： https://blog.csdn.net/_/article/details/
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/203162.html原文链接：https://javaforall.net
