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)。

（2）性质

1. 反身性：a≡a (mod m)；
2. 对称性：若a≡b(mod m)，则b≡a (mod m)；
3. 传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；
4. 同余式相加减：若a≡b(mod m)，c≡d(mod m)，则a$pm$c≡b$pm$d(mod m)；
5. 同余式相乘：若a≡b(mod m)，c≡d(mod m)，则a$*$c≡b$*$d(mod m)。
6. 同余式数乘：若a≡b(mod m)，则ak≡bk(mod m)，k为任意整数。
7. 除法：若 a$*$c≡b$*$c(mod m) ，c $cancel{=}$ 0，则a≡b( mod m/(gcd(c,m)) ) ，其中gcd(c,m)表示c和m的最大公约数，
   特殊地，gcd(c,m)=1，则 a≡b(mod m) ；
8. 幂运算：如果a≡b(mod m) ，那么 $a^n$≡$b^n$(mod m) ；
9. 若 a≡b(mod m) ，n=m，则 a≡b(mod n) ；
10. 若 a≡b(mod $m_i$) ，(i=1,2…n) 则 a≡b(mod [$m_1,m_2,…,m_n$]) ，其中 [$m_1,m_2,…,m_n$] 表示m1,m2,…mn的最小公倍数。
11. 若 a≡b(mod m) ，k为正整数，则 ka≡kb(mod km) ；
    d为a,b,m的任一公约数，则$frac{a}{d}≡frac{b}{d}(modspace frac{m}{d})$；
12. 设d>=1，d|m，若 a≡b(mod m) ，则 a≡b(mod d) ；
13. 若 a≡b(mod m)，则 (a,m)≡(b,m) ；
14. 如果 a mod b = c ，则有(a+kb) mod b =c(k为非0整数)
15. 如果 a mod b = c ，则有(ka) mod b =(kc) mod b (k为正整数)
16. (a+b) mod c =((a mod c)+(b mod c )) mod c;
17. (ab) mod c=((a mod c)(b mod c)) mod c

3. 欧拉函数

（1）定义

φ(n)是欧拉函数（Euler’s totient function），设n是正整数，φ(n)表示{0,1,…,n-1}中与n互素的数的个数。例如φ(12)=4，因为与12互素的数有1，5，7，11。这里认为φ(1)=1。

（2）公式

$φ(n)=n(1-frac{1}{p_1})(1-frac{1}{p_2})…(1-frac{1}{p_k})$
其中p1, p2……pn为n的所有质因数，n是不为0的整数。

（3）性质

1. 对于质数n，φ(n)=n-1
2. 对于质数p，若$n=p^k$，$φ(n)=p^k-p^{k-1}=(p-1)p^{k-1}$
3. 【积性函数】:
   若m,n互质，φ(mn)=φ(m)φ(n)
4. 【计算式】:
   对于质数p，若$n=prod p_i^{k_i}=p_1^{k_1}*p_2^{k_2}*p_3^{k_3}*…*p_n^{k_n}$，
   则$φ(n)=n*prod(1-frac{1}{p_i})=n(1-frac{1}{p_1})(1-frac{1}{p_2})…(1-frac{1}{p_k})$
5. 【欧拉定理】：
   对于互质的a,n，有$a^{φ(n)} ≡ 1 (modspace n)$
6. 小于n且与n互质的数的和：$S=φ(n) * frac{n}{2}$，(n>1)
7. 对于质数p，
   若n mod p=0，则φ(n∗p)=φ(n)∗p
   若n mod p≠0，则φ(n∗p)=φ(n)∗(p−1)
8. $n=sum _{d∣n}φ(d)$，即n的因数（包括1和它自己）的欧拉函数之和等于n

（5）计算单个欧拉函数

int oula(int n) { int rea=n; for(int i=2; i*i<=n; i++) if(n%i==0)//第一次找到的必为素因子 { rea=rea-rea/i; do n/=i;//把该素因子全部约掉 while(n%i==0); } if(n>1) rea=rea-rea/n; return rea; }

（6） 欧拉函数打表O(NlogN)

说明：
定义：欧拉函数phi(n)，表示小于或等于n的数中与n互质的数的数目。
欧拉函数求值的方法是：
（1）phi(1)=1
（2）若n是素数p的k次幂，$phi(n)=p^k-p^{k-1}=(p-1)p^{k-1}$
（3）若m，n互质，phi(mn)=phi(m)phi(n)
根据欧拉函数的定义，可以推出欧拉函数的递推式：
令p为N的最小质因数，若$p^2|N,phi(N)=phi(frac{N}{p}) imes p$