You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1.6 KiB
1.6 KiB
1. 同余符号：\equiv
（1）含义
两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余，记作a≡b(mod \ m)。读作a同余于b模m，或读作a与b关于模m同余。
例：26≡14(mod \ 12)。
（2）定义
设m是大于1的正整数，a，b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod \ m)，读作a同余于b模m。
（3）性质
(1) 若a≡0(mod\ m)，则m|a;
(2) a≡b(mod\ m)等价于a与b分别用m去除，余数相同
2. 同余定理
（1）定义
给定一个正整数m，如果两个整数a和b满足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)，c≡d(mod \ m)，则a±c≡b±d(mod\ m)；
同余式相乘：若a≡b(mod\ m)，c≡d(mod\ m)，则a∗c≡b∗d(mod \ m)。
同余式数乘：若a≡b(mod\ m)，则a\times k≡b \times k(mod \ m)，k为任意整数。
除法：若 a∗c≡b∗c\ (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)$ ；