初等数论

若没有特殊说明，则本节的所有数都是整数

前置

• 整数

定义

• 整除：对于整数$a,b\in \mathbb{Z}\wedge a\ne 0$，如果存在整数$q\in \mathbb{Z}$，使得$b=qa$，则称$b$能被$a$整除，记作$a\mid b$。称$a$为$b$的因子或约数。
• 显然约数：称$\pm b,\pm 1$为$b$的显然约数
• 素数：称$p$为素数，当且仅当$p\notin \{-1,0,1\}$且$p$的除了显然约数$\pm 1,\pm p$外没有其他约数,默认素数为正数，因为$p$素等价于$-p$素
• 合数：称$p$为合数，当且仅当$p\notin \{-1,0,1\}$且$p$不是素数
• 公约数:$\mathfrak{D}(a_1,a_2,\cdots ,a_n)=\{d\mid \forall i\in [n],d|a_i\}$
• 最大公约数：若$a_i$不全为$0$，则可定义最大公约数$\gcd (a_1,a_2,\cdots ,a_n):=\max (\mathfrak{D})$,简记为$(a_1,a_2,\cdots ,a_n)$
• 公倍数：若$a_i$全不为$0$，则可定义公倍数$\mathfrak{M}(a_1,a_2,\cdots ,a_n)=\{m\mid \forall i\in [n],a_i|m\}$
• 最小公倍数：若$a_i$全不为$0$，则可定义最小公倍数$\text{lcm}(a_1,a_2,\cdots ,a_n):=\min \{m\in \mathfrak{M}|m>0\}$，简记为$[a_1,a_2,\cdots ,a_n]$
• 互素：称$a_1,a_2,\cdots ,a_n$互素，当且仅当$(a_1,a_2,\cdots ,a_n)=1$
• $m>0$, 任意整数$n$都可以表示为$n=qm+r$，其中$q$是商，$r$是余数，$0\le r<m$，即对于任意$n\in \mathbb{Z}$, 都存在$r\in Z_m=\{i\in \mathbb{Z}\mid 0\le i<m\}$，使得$n=qm+r$，称$r$为$n$模$m$的余数，记作$r=f_m(n)=:(n\mathrm{mod}m)=:n\%m$

性质

1. $a|b⟺(-a)|b⟺a|(-b)⟺(-a)|(-b)⟺|a|\mid |b|$
2. $a|b\wedge b|c\Rightarrow a|c$
3. $\forall i\in [k],a|a_i⟺\forall x_i\in \mathbb{Z},i\in [k],a|a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n$
4. $m\ne 0\wedge a|b\Rightarrow (ma)|(mb)$
5. $a|b\wedge b|a\Rightarrow a=\pm b$
6. $b\ne 0\wedge a|b⟹|a|\le |b|$
7. $a\ne 0\wedge b=qa+r⟹(a|b⟺a|r)$
8. $m|a\wedge m|b\wedge a|b⟹(a/m)|(b/m)$
9. $a>1$,则$a$为合数$⟺\exists a>d>1,\exists a>e>1,s.t.a=de$
10. $d>1$,$q$素,则$d|q⟹d=q$
11. 若$a$合，则存在素$p$, s.t. $p|a$
12. 对于整数$a\ge 2$,则$a$可以表示为若干素数的乘积，$a={\prod }_{i=1}^n{p}_i$
13. 素数有无穷多个
14. 最大公约数的性质：$(a_1,a_2)=(-a_1,a_2)=(a_1,-a_2)=(-a_1,-a_2)=(|a_1|,|a_2|)$
15. 最大公约数的性质：$(a_1,a_2,\cdots ,a_n)=(a_1,a_2,\cdots ,a_n,a_{i}x)$
16. 最大公约数性质：$(a_1,a_2,\cdots ,a_n)=(a_1,a_2,\cdots ,a_i+x{a}_j,\cdots ,x_j,\cdots ,a_n)$
17. 最大公约数性质：若存在整系数线性组合使得$x_1{a}_1+x_2{a}_2+\cdots +x_n{a}_n=1$，则$(a_1,a_2,\cdots ,a_n)=1$
18. 最大公约数的性质：设$m>0\wedge m|(a_1,a_2,\cdots ,a_n)$,则$m(a_1/m,a_2/m,\cdots ,a_n/m)=(a_1,a_2,\cdots ,a_n)$
19. 最小公倍数的性质：若$m>0$,则$m[a_1,a_2,\cdots ,a_n]=[m{a}_1,m{a}_2,\cdots ,m{a}_n]$
20. 带余数除法定理：对于任意整数$a\ne 0,b$,存在唯一整数$q,r$,使得$b=qa+r,0\le r<|a|$
21. 最大公约数等价定义：若$a_i$不全为$0$,则$(a_1,a_2,\cdots ,a_n)=min\{d:d=x_1{a}_1+x_2{a}_2+\cdots +x_n{a}_n,x_i\in \mathbb{Z}\wedge d>0\}$
22. 最大公约数的定理：$(m,a)=1⟹(m,ab)=(m,b)$
23. 最大公约数的定理：$(m,a)=1\wedge m|ab⟹m|b$
24. $[a_1,a_2](a_1,a_2)=|a_1{a}_2|$
25. $(\forall a_i|c)⟺[a_1,a_2,\cdots ,a_n]|c$,即公倍数是最小公倍数的倍数
26. 算术基本定理：$a\ge 2,a={\prod }_{i=1}^n{p}_i$，其中$p_i$为素数，且$p_1\le p_2\le \cdots \le p_n$
27. $(a\%m+b\%m)\%m=(a\%m+b)\%m=(a+b\%m)\%m=(a+b)\%m$