//若无特殊说明，均是在整数范围内讨论
整除
对于a，b（a不为0），若存在k，使得b=ka，则说a整除b，或者说b被a整除，记作a|b。此时，称a为b的约数（除数、因数），b为a的倍数。
性质：
1、若a|b，a|c，那么对于任意的x，y，都有a|xb+yc。
2、若a|b，b|c，则有a|c。
3、a|b，当且仅当ka|kb（k不为0）。
4、若a|b且b|a，则a=b或a=-b。
5、若a|b且b不为0，则|a|<=|b|。
//0可以被任意数非0数整除
取余
对于a，b（a不为0），我们可以写成b=ka+r的形式，r称为a除b的余数，记作r=a mod b，且满足0<r<|b|。特别的，当r=0，就是a|b。
性质：
1、(a + b) mod p = (a mod p + b mod p) mod p
2、(a - b) mod p = (a mod p - b mod p + p) mod p
3、(a * b) mod p = (a mod p * b mod p) mod p
//模的除法与乘法逆元有关
最大公约数和最小公倍数
a，b均不为零，对于所有的c|a且c|b，称c为a和b的公约数，所有公约数中最大的称为最大公约数，记作c=gcd(a,b)。
a，b均不为零，对于所有的a|c且b|c，称c为a和b的公倍数，所有公倍数中最小的称为最小公倍数，记作c=lcm(a,b)。
性质：
1、若a|m，b|m，则gcd(a,b)|m；若m|a，m|b，则m|lcm(a,b)
2、ab=gcd(a,b)*lcm(a,b) //可由算术基本定理（正整数的唯一分解定理）得出，实际使用时要避免溢出（可先做除法）
3、lcm(ma,mb)=m*lcm(a,b)
4、若m是a1,a2,a3,...,an的公倍数，则lcm(a1,a2,a3,...,an)|m
5、gcd(a,b)=gcd(b,a%b) //欧几里得算法核心
质数
质数又称素数、不可约数。质数是大于1的整数中，只有1和他本身两个因数的数。合数是除1和质数以外的自然数（不包括0）。1既不是质数也不是合数。
性质：
1、质数有无穷多个
2、若a>1，b是质数，且a|b，则a=b
3、若p为质数且p|ab，则p|a或p|b
欧拉函数
欧拉函数Φ(n)是指小于等于n的数中（正整数）与n互质的数的个数。Φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)...(1-1/px)，p1到px是指n的所有质因数。
若p