整除的性质
1、$a|b\ , \ b|c\ \Rightarrow\ a|c$
2、$a|b\ , \ a|c\ \Rightarrow\ a|bx+cy,\ \forall x,y\in Z$
3、$a|b\ , \ b|a\ \Rightarrow\ a=\pm b$
4、若 $b\neq0$ ,则 $a|b\ \Rightarrow\ a\le\ b$
公约数()和公倍数[]
1、$Fermat\ number\ F_n=2^{2^n}$
2、$(F_m,F_n)=1$
3、若 $ (a,b)=1$ ，则 $(a,kb)=(a,k)$
4、若 $(a,b)=1$ ，则 $(a^m,b^n)=1$
5、若 $(a,b)=1$ ，则 $a|kb\ \Rightarrow\ a|k$
6、$(a^k,b^k)=(a,b)^k$
7、若 $(a,b)=1$ ， $ab=c^k$ ，则 $a=(a,c)^k,\ b=(b,c)^k$
8、$(a^m-1,a^n-1)=a^{(n,m)}-1,\ 若\ a\ge2$
9、$(a,[b,c])=[(a,b),(a,c)]$
10、$(a,b)\times[a,b]=ab$
$Euclid’s\ algorithm$
1、$\exists\ x_0,x_1,…\ s.t.(a,b,…)=ax_0+bx_1+…$
算术基本定理
1、任何整数都可以拆分成若干素数幂的乘积
2、$let\ a=\prod{p_i^{\alpha_i}},\ b=\prod{p_i^{\beta_i}},\ 则\ $
3、$(a,b)=\prod{p_i^{min(\alpha_i,\beta_i)}}$
4、$[a,b]=\prod{p_i^{max(\alpha_i,\beta_i)}}$
5、定义除数函数 $\tau(a)$ ，表示 $a$ 的正因子个数，则 $\tau(a)=\prod{\tau(p_i^{\alpha_i})}=\prod{(\alpha_i+1)}$
6、定义符号 $||\ :a^k||b\ \Leftrightarrow\ a^k|b\ , \ a^{k+1}\nmid b$
7、$a^\alpha||n!\ \Leftrightarrow\ \alpha=\sum_{j=1}^{\infty}[\frac{n}{p^j}]$
8、$n!=\prod_{p\le n}p^{\alpha}\ \ \alpha$: {$\alpha\ |\ p^\alpha||n!$}
同余
1、$a\pm b\equiv c\pm d\ mod\ m$ ，若 $c\equiv d\ mod\ m$ ， $a\equiv b\ mod\ m$
2、$a\times b\equiv c\times d\ mod\ m$ ，若\ $c\equiv d\ mod\ m$ ， $a\equiv b\ mod\ m$
3、$a\equiv a\ mod\ m$
4、$a\equiv b\ mod\ m\ , \ b\equiv c\ mod\ m\ \Rightarrow\ a\equiv c\ mod\ m$
5、设 $f(x)=\sum_{i=0}^{n}a_ix^i$ ， $g(x)=\sum_{i=0}^{n}b_ix^i$，则
$\ \ \ \ \ f(x)\equiv g(x)\ mod\ m\ \Leftrightarrow\ a_i\equiv b_i\ mod\ m\ (0\le i\le n)$
$\ \ \ \ \ f(x)\equiv g(x)\ mod\ m,\ a\equiv b\ mod\ m\ \Rightarrow\ f(a)\equiv g(b)\ mod\ m$
6、若 $d\ge 1$ ， $d|m$ ，则 $a\equiv b\ mod\ m\ \Rightarrow a\equiv b\ mod\ d$
7、$c\times a\equiv c\times b\ mod\ m\ \Rightarrow a\equiv b\ mod\ (\frac{m}{(m,c)})$
8、若 $m\ge 1$ ，$(a,m)=1$ ，则 $\exists c$ ，使得 $a\times c\equiv 1\ mod\ m$
9、$a\equiv b\ mod\ m_i\ (i=1,2,3….)\ \Leftrightarrow\ a\equiv b\ mod\ ([m_1,m_2,…])$
$Euler’s\ Function$
1、$\phi(m)=|{1\le i\le m|(i,m)=1}|$
2、$\phi(p^k)=p^{k-1}*(p-1)$
3、$m=m_1*m_2\ \Rightarrow \phi(m)=\phi(m_1)*\phi(m_2)$
4、 设 $m=\prod_{i=1}^{r}p_i^{\alpha_i}$ ，则
$\ \ \ \ \ \ \phi(m)=\prod_{i=1}^{r}p_i^{\alpha_i-1}*(p_i-1)$
$\ \ \ \ \ \ \phi(m)=m*\prod_{p|m}(1-\frac{1}{p})$
5、$\sum_{d|n}\phi(d)=n$
$Euler’s\ theorem$
1、$a^{\phi(n)}\equiv 1\ mod\ n$
2、$Fermat’s\ little\ theorem:\ a^{P-1}\equiv 1\ mod\ p$
3、$(-1)^{\phi(n)}\equiv 1\ mod\ n$
4、$a^{-1}\equiv a^{\phi(n)-1}\ mod\ n$
剩余系
1、剩余（同余）类： $\overline{r}:$ {$x|x\equiv r\ mod\ n$}
$\ \ \ \ \ $既约剩余类：满足 $(r,n)=1$ 的 $\overline{r}$
2、完全剩余系：从$n$的每个剩余类中各选取一个元素组成的集合
3、既约剩余系： 从$n$的每个剩余类中各选取一个元素组成的集合
4、若 $m$ 个整数两两模 $m$ 不同余，则它们构成模 $m$ 的一个完全剩余系
$\ \ \ \ \ $若 $\phi(m)$ 个整数两两模 $m$ 不同余，则它们构成模 $m$ 的一个既约剩余系
5、$\forall a,b\in Z,\ (a,m)=1,\ x$ 是模 $m$ 的完全（既约）剩余系 $\Leftrightarrow ax+b$ 是模 $m$ 的一个完全（既约）剩余系
6、若 $m=m_1*m_2$ ，且 $ (m_1,m_2)=1$ ，则
$\ \ \ \ \ \ x$ ， $y$ 分别是模 $m_1$ ,模 $m_2$ 的完全剩余系 $\Rightarrow$ $m_2x+m_1y$ 是模 $m$ 的完全剩余系
$Wilsom’s\ Theorem$
1、$(p-1)!\equiv -1\ mod\ p$
2、$(m-1)!\equiv 0\ mod\ m,\ m$ 为大于4的合数
3、令 ${r_1,r_2,…r_c}$ 为 $p^l$ 的一组既约剩余系, $c=\phi(p^l),\ p$ 为不小于3的素数,则
$\ \ \ \ \ \ \prod_{i-1}^{c}r_i\equiv -1\ mod\ p^l$
$\ \ \ \ \ \ \prod_{i=1}^{p-1}\prod_{s=0}^{p^{p-1}-1}\equiv -1\ mod\ p^l$，这个公式本是上面的特殊情况，即 $r_i<\phi(p^l)$
4、令 ${r_1,r_2,…r_c}$ 为 $2^l$ 的一组既约剩余系，$c=\phi(2^l)$ ，则
$\ \ \ \ \ \ \prod_{i=1}^{c}r_i\equiv -1\ mod\ (2^l)\ \ l=1,2$
$\ \ \ \ \ \ \prod_{i=1}^{c}r_i\equiv 1\ mod\ (2^l)\ \ l\ge3$
5、令 ${r_1,r_2,…r_c}$ 为 $2p^l$ 的一组既约剩余系，$c=\phi(2p^l)$ ， $p$ 为不小于3的素数,这则
$\ \ \ \ \ \ \prod_{i=1}^{c}r_i\equiv -1\ mod\ (2p^l)$
6、$\prod_{i=1}^{\frac{p+1}{2}}(2i-1)^2\equiv(-1)^{\frac{p+1}{2}}\ mod\ p$
7、若 $p\equiv3\ mod\ 4$ ，则 $(\frac{p-1}{2})!\equiv \pm1\ mod\ p$
8、若 $1<k<p$ ，则 $(p-k)!*(k-1)!\equiv(-1)^k\ mod\ p$
同余方程
1、一元高次同余方程（$f(x)=\sum_{i=0}^n a_ix^i\ =0\ mod\ m$）
$\ \ \ \ \ \ \ \ 1.1$ 费马同余恒等式 $h(x)=x^p-p\ =0\ mod\ p$
$\ \ \ \ \ \ \ \ 1.2$ 降幂 $若\ f(x)=g(x)*h(x)+r(x),\ 则\ f(x)=0\ mod\ m\ \Leftrightarrow r(x)=0\ mod\ m$
$\ \ \ \ \ \ \ \ 1.3$ $若\ (k,m)=1,\ 则\ f(x)=0\ mod\ m\ \Rightarrow kf(x)=0\ mod\ m$
2、一次同余方程（$ax=b\ mod\ m$)
$\ \ \ \ \ \ \ \ 2.1$ $(a,m)=1$，$x=a^{-1}b\ mod\ m$
3、一次同余方程组（$x=a_i\ mod\ m_i$，其中$m_i$两两互素)
$\ \ \ \ \ \ \ \ 3.1$ 中国剩余定理 令$M=\prod_{i=1}^n m_i,\ M_i=\frac{M}{m_i}$，则$(M_i,M)=1$，再令$u_i=M_i^{-1}\ mod\ m_i$，$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x=\sum_{i=1}^n a_iu_iM_i mod\ M$
二次剩余
1、定义 如果方程 $x^2=d\ mod\ p$ 有解，则称 $d$ 是模 $p$ 的二次剩余，否则称二次非剩余。
2、在模$p$ 的既约系中，二次剩余和二次非剩余各占一半。
3、$Euler$判别法
$\ \ \ \ \ \ d$ 是模 $p$ 的二次剩余$\Leftrightarrow d^{\frac{p-1}{2}}=1\ mod\ p$
$\ \ \ \ \ \ d$ 是模 $p$ 的二次非剩余$\Leftrightarrow d^{\frac{p-1}{2}}=-1\ mod\ p$
4、若 $p=1\ mod\ 4$，则 $-1$ 是模 $p$ 的二次剩余
$\ \ \ \ \ \ $若 $p=3\ mod\ 4$，则 $-1$ 是模 $p$ 的二次非剩余
5、$Legendre$ 符号
$\ \ \ \ \ \ 5.1$ 记 $(\frac{d}{p})$ 为$Lengendre$ 符号
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{d}{p})=0\ \ p|d$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{d}{p})=1\ \ d是p的二次剩余$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{d}{p})=-1\ \ d是p的二次非剩余$
$\ \ \ \ \ \ 5.2$ 引理
$\ \ \ \ \ \ \ \ \ \ \ \ \ $设 $1\le i<p/2$ ，$t_i=id\ mod\ p$ ，$n$ 表示 $t_i$ 中大于 $p/2$ 的数的个数，则$(\frac{d}{p})=(-1)^n$
$\ \ \ \ \ \ 5.3$ 性质
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{d}{p})=d^{\frac{p-1}{2}}\ mod\ p$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{d}{p})=(\frac{d+p}{p})$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{dc}{p})=(\frac{d}{p})(\frac{c}{p})$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{-1}{p})=1，\ p=1\ (mod\ 4)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{-1}{p})=-1，\ p=3\ (mod\ 4)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$
$\ \ \ \ \ \ \ \ \ \ \ \ \ $素数 $p>2$ ，且 $(d,2p)=1$ , $(\frac{d}{p})=(-1)^T$ ,其中 $T=\sum_{j=1}^{(P-1)/2} [\frac{jd}{p}]$
$\ \ \ \ \ \ 5.4$ $Guass$ 二次互反律
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{(p-1)(q-1)}{4}}$
6、$Jacobi$ 符号
$\ \ \ \ \ \ 6.1$ 记$(\frac{d}{P})=(\frac{d}{p_1})(\frac{d}{p_2})…$ 为$Jacobi$ 符号，其中 $P=p_1p_2…，p_i是奇素数$
$\ \ \ \ \ \ 6.2$ 性质
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{1}{P})=1$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{d}{P})=0，(d,P)\ne 1$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{d}{P})=\pm 1,\ (d,P)=1$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{d}{P})=(\frac{d+P}{P})$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{dc}{P})=(\frac{d}{P})(\frac{c}{P})$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{-1}{P})=(-1)^{\frac{P-1}{2}}$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{2}{P})=(-1)^{\frac{P^2-1}{8}}$
$\ \ \ \ \ \ \ \ \ \ \ \ \ (\frac{P}{Q})(\frac{Q}{P})=(-1)^{\frac{(P-1)(Q-1)}{4}}，P,Q是奇数$