同余定理总结方法

大家好，欢迎来到IT知识分享网。

同余定理是数论中的重要概念。给定一个正整数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)::

同余性质：
反身性：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的最小公倍数

1.对于同一个除数，两个数之和（或差）与它们的余数之和（或差）同余。
2.对于同一个除数，两个数的乘积与它们余数的乘积同余。
3.对于同一个除数，如果有两个整数同余，那么它们的差就一 定能被这个除数整除。
4.对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。

Application：

• 例题：求2001^2003除以13的余数
• 根据同余性质❹，我们可以得出2001^2003≡122003（mod 13）
• 12^{2003还是一个较大的数，很难求出它除以13的余数，这时，我们就要找出12的几次方与1对于模13是同余的。根据试验，可得出12}2≡1（mod 13）
• 我们把12^2003拆成 (12^{2）×1001×12}1，而(12^{2）×1001×12}1≡1×12≡12（mod 13）
• 这时，我们可以得出*2001^2003除以13的余数为12，*我们用计算器计算一下，这个答案是对的。