1 同余定理定义
如果两个整数a和b，(a-b)能被m整除，则a和b被m除的余数相同，记做
如果有，则
2 同余定理证明
充分性：
假定（其中r1和r1小于m，h1和h2为整数）a = h1*m+r1b = h2*m+r2则a-b = (h1-h2)*m + (r1-r2)因为，则r1-r2=0，即r1=r2，得证
必要性：
整数a，b，被整数m除的余数相同，其中h1和h2为整数，r为余数，则有a=h1*m+rb=h2*m+r(a-b)=h1*m+r-h2*m-r=(h1-h2)*m因为h1和h2为整数，（h1-h2）为整数；所以，a-b能被m整除，得证。
3 同余定理性质（只列与证费马小定理相关的）
3.1 乘法定理
如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)。
证明：条件告诉我们，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式两边分别展开后必然是ax-m(…) = by-m(…)的形式，这就说明ax≡by(mod m)。
现在你知道为什么有的题要叫你“输出答案mod xxxxx的结果”了吧，那是为了避免高精度运算，因为这里的结论告诉我们在运算过程中边算边mod和算完后再mod的结果一样。假如a是一个很大的数，令b=a mod m，那么(a * 100) mod m和(b * 100) mod m的结果是完全一样的，这相当于是在a≡b (mod m)的两边同时乘以100。这些结论其实都很显然，因为同余运算只关心余数（不关心“整的部分”），完全可以每一次运算后都只保留余数。因此，整个运算过程中参与运算的数都不超过m，避免了高精度的出现。
3.2 除法定理
如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m)（就是说同余式两边可以同时除以一个和模数互质的数）。
证明：条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq，也就是说(a-b)c = m(p-q)。这表明，(a-b)c里需要含有因子m，但c和m互质，因此只有可能是a-b被m整除，也即a≡b(mod m)。
4 费马小定理
费马小定理：假如p是质数，且gcd(a,p)=1，即a,p互质，那么。
证明：
给出数列:
我们假定数列中的两项ma和na被p除后的余数相同，即ma≡ na(mod p)，根据同余定理：
ma-na=(m-n)a能被p整除，即
(m-n)a|p
因为a与p互质，所以只能（m-n)是p的倍数（m-n不等于0，因为前提假设是不同的两项）。但是m，n属于数列{1,2,3,4......p-1},所以m-n不可能是p的倍数，则假设ma≡ na(mod p)不成立，也就是数列中任意两项被p除的余数都不可能相等。
而任意整数被p除的余数只能是{1,2,3,4......p-1}，总共p-1项。
数列总共有p-1项，所以数列中的数被p除的余数是{1,2,3,4......p-1}
根据上面提到同余的乘法定理有:
简化得：
根据上面提到同余的除法性质有（显然有p-1阶乘中的每一项都与p互质）：
参考：
/zhixingqiezhixing/archive//04/03/2430676.html
