【搬运自己的CSDN】
倍数与约数
对于整数$a,b$，若存在整数$c$使得$ac=b$成立，则称$b$是$a$的倍数，$a$是$b$的约数，也称$a$是$b$的因数（因子）。
整除
对于整数$a,b$，如果$b$除以$a$的余数为$0$，则称$a$整除$b$，记作$a|b$。
显然，$a是b的约数\Longleftrightarrow a|b$
质数与合数
质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。
同余式，取模
- 首先什么是有余除法
- 讲完了。
- 然后什么是取模
取模就是取余。
形式化的，对于数$a$和模数$m$，易证存在唯一的$0 \leqslant b <m$使得$\exists k,b+km=a$，此时$b$即为$a$对$m$取模（取余）的结果，记为：$$ a \mod m = b $$
你要说“模”和“余”有什么不同，我会告诉你上式中$m$称作模数，$b$称作余数。
- 然后什么是同余
同余就是如果$a,b$对模数$m$取模后的结果相同，则称$a,b$在模$m$意义下同余，记作：
$$ a \equiv b\pmod m $$
- 然后什么是同余式
- 有“$\equiv$”的都是。
模运算意义下的 加、减、乘 操作
如果我要对一个整数进行足够多的加，减，乘操作，最后输出答案对$p$取模后的结果，要求中途的中间运算结果不能超过$p$,能不能做到？
这个问题对计算机是很现实的问题，计算机的整形数最大只能存$16Byte$（cpp环境下），所以需要计算期间数都不能太大。
如果你数学还不错，那么你一定知道以下几个公式：
$$ 如果a+b \equiv c \bmod p $$
$$ 那么a \equiv d \bmod p,b \equiv e \bmod p $$
$$ 则 d+e \equiv c \bmod p $$
数学语言的是真够难受的，用计算机语言表示，就是(a+b)%p=(a%p+b%p)%p。
（这里的%表示取模运算，是一个二元运算符，返回其前一个数对后一个数取余的结果）
用人话说，算两个数的 和之模，可以算其 模之和之模。
怎么证明呢？有点显然，过程如下：
$$ 记a=k_a\cdot p+b_a(k_a,b_a \in \mathbb{Z},b_a < p) $$
$$ b=k_b\cdot p+b_b(k_b,b_b \in \mathbb{Z},b_b < p) $$
$$ 则实际上，a\equiv b_a \bmod p,b\equiv b_b \bmod p $$
$$ a+b=k_a\cdot p+b_a+k_b\cdot p+b_b\equiv b_a+b_b\pmod p $$
$$ 所以b_a+b_b\equiv c\pmod p $$
即得证
其实，如果直接把$\equiv$叫作同余号，上面也不用证明了。。。
减法的话，完全一样。差之模等于模之差之模。
当然，计算机中为避免模运算的负数结果，经常用这样的技巧：(a-b)%p==(a%p+p-b%p)%p
那乘法呢？
公式一模一样：
$$ 如果a\times b \equiv c \bmod p $$
$$ 那么a \equiv d \bmod p,b \equiv e \bmod p $$
$$ 则 d\times e \equiv c \bmod p $$
计算机语言：(a*b)%p=((a%p)*(b%p))%p，
当然，由于计算机优先级的缘故，代码可以直接写成(a*b)%p=a%p*b%p
首先把$a\times b$看成$b$个$a$相加，那套用上面公式，$a$可以用$a\%p$替代；
再把$a\%p\times b$看成$a\%p$个$b$相加，一样，$b$可以用$b\%p$替代。
得证。积之模与模之积同余。
性质(百度百科)
- 同余式可以逐项相加。
- 同余式一边的数可以移到另一边，只要改变符号就可以了。
- 同余式的每一边都可以增加或减去模的任意倍数。
- 同余式可以逐项相乘。
- 同余式两边的数如有公约数，此公约数又和模互素，那么就可以把两边的数除以这个公约数。
- 同余式两边的数和模可以同时乘上一个整数。
- 同余式两边的数和模可以同时被它们任一公约数除。
- 如果同余式对于模m成立，那么它对于m的任意约数相等的模d也成立。
- 如果同余式一边上的数和模能被某个数除尽，则同余式的另一边的数也能被这个数除尽。
- 同余式一边上的数与模的最大公约数，等于另一边上的数与模的最大公约数。
测了不想写了
以后的看不懂活该