数论

整除的性质

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是奇数$