初等数论一

整除性

定义1

对于整数a$\neq$​= 0，b，a整除b，则存在整数k使得b$=$=ka，记为a$\mid$∣b。否a则a不整除b，记为 a$\nmid$∤b.
性质

• 对任意a$\neq$​= 0,a$\mid$∣ 0,a$\mid$∣a
• 对任意b，1$\mid$∣b
• 传递性 a$\mid$∣b,b$\mid$∣c，则a$\mid$∣c
• a$\mid$∣b,b$\mid$∣c，则a$\mid$∣(sb+tc)，st为任意整数

定理1

设a，b是两个整数，且b$>$> 0，则存在两个唯一的整数q及r，使得$a=bq+r,0\leq r<b$a=bq+r,0≤r<b证明：
   存在性
做序列……，-2b，-b，0，b，2b，……，则a必然在序列某两项之间，即存在整数q，使得$qb\leq a <(q+1)b$qb≤a<(q+1)b，令$r=a-qb$r=a−qb，则存在。
   唯一性
假设存在另一对整数$q_1$q1​,$0\leq r_1<b$0≤r1​<b，即有$q_1 +r_1 =a =qb+r$q1​+r1​=a=qb+r，于是$b(q_1-q)=r-r_1$b(q1​−q)=r−r1​，故$b|q_1-q|=|r-r_1|$b∣q1​−q∣=∣r−r1​∣,而$|r-r_1|<b$∣r−r1​∣<b，因此$r=r_1,q=q_1$r=r1​,q=q1​即唯一。

最大公约数

定义2

$a_1,a_2,a_3,...,a_n$a1​,a2​,a3​,...,an​是n个不全为0的整数，整数d是每一个的因数，称d为其的一个公因数。最大的公因数记为 $(a_1,a_2,a_3,...,a_n)$(a1​,a2​,a3​,...,an​)，若最大公因数为1，则 $a_1,a_2,a_3,...,a_n$a1​,a2​,a3​,...,an​互素。

定理2

a，b，c是三个不全为零的整数，且$a=bq+c$a=bq+c，q为整数，则$(a,b)=(b,c)$(a,b)=(b,c)
证明：

---

Euclidean算法

辗转相除
定理3 任意$a>0,b>0$a>0,b>0，则（a，b）就是辗转相除余数为零时的除数
证明：根据定理2递推即可。

定理4 任意$a>0,b>0$a>0,b>0，存在两个整数m，n使得$(a,b)=ma+nb$(a,b)=ma+nb
可根据辗转相除递推式逆推得出。

推论 a和b的公因子式】是（a，b）的因数

---

扩展Euclidean算法

推荐两个博客：1 2

扩展Euclidean算法是用来计算在已知a, b求解一组x，y使得ax+by =c.（c是$(a，b)$(a，b)的倍数）。$ax+by=k(a,b),k为整数$ax+by=k(a,b),k为整数，可转化为求$ax_n+by_n=(a,b)$axn​+byn​=(a,b)中的x_n和y_n。
根据定理2，$(a,b)=(b,a\%b)$(a,b)=(b,a%b)，于是$ax+by=(b,a\%b)=bx_1+a\%by_1=bx_1+(a-\frac{a}{b}b)y_1=ay_1+b(x_1-\frac{a}{b}y_1)$ax+by=(b,a%b)=bx1​+a%by1​=bx1​+(a−ba​b)y1​=ay1​+b(x1​−ba​y1​)，所以有
$\begin{cases} x=y_1 , \\ y=x_1-\frac{a}{b}y_1, \end{cases}${x=y1​,y=x1​−ba​y1​,​边界条件，$x_n=1,y_n=0$xn​=1,yn​=0

---

定理5

若$a\mid bc,(a,b)=1,则a\mid c$a∣bc,(a,b)=1,则a∣c
证明，根据定理4，因为a，b互素，有ma+nb=1，所以mac+nbc=c，$mc+\frac{nbc}{a}=\frac{c}{a}$mc+anbc​=ac​

定理6

设$n>2,a_1>0,a_2>0,...,a_n>0, (a_1,a_2)=d_2,(d_2,a_3)=d_3,...,(d_{n-1},a_n)=d_n$n>2,a1​>0,a2​>0,...,an​>0,(a1​,a2​)=d2​,(d2​,a3​)=d3​,...,(dn−1​,an​)=dn​，那么有$(a_1,a_2,...,a_n)=d_n$(a1​,a2​,...,an​)=dn​
证明
$d_n\mid d_{n-1},d_n\mid a_n,而d_{n-1}\mid d_{n-2},d_{n-1}\mid a_{n-1}，得d_n\mid d_{n-2},d_n\mid a_{n-1}$dn​∣dn−1​,dn​∣an​,而dn−1​∣dn−2​,dn−1​∣an−1​，得dn​∣dn−2​,dn​∣an−1​递推即可得到$d_n\mid a_1,...,d_n\mid a_n$dn​∣a1​,...,dn​∣an​。
设$(a_1,...,a_n)=d,则d_n\leq d，且d\mid d_2,...,d\mid d_n, d\leq d_n,所以d_n=(a_1,...a_n)$(a1​,...,an​)=d,则dn​≤d，且d∣d2​,...,d∣dn​,d≤dn​,所以dn​=(a1​,...an​)

定理7

存在整数$x_1,...,x_n使得a_1x_1+...+a_nx_n=(a_1,...a_n)$x1​,...,xn​使得a1​x1​+...+an​xn​=(a1​,...an​)
证明，根据定理4结合定理6.

最小公倍数

定义3

最小公倍数，记作$[a_1,a_2,...,a_n]$[a1​,a2​,...,an​]

定理8

a,b 是任意两个整数，则a，b得所有公倍数都是[a,b]得公倍数，且$[a,b]=\frac{ab}{(a,b)}$[a,b]=(a,b)ab​

定理9

设$n>2,a_1>0,a_2>0,...,a_n>0, [a_1,a_2]=m_2,[m_2,a_3]=m_3,...,[m_{n-1},a_n]=m_n$n>2,a1​>0,a2​>0,...,an​>0,[a1​,a2​]=m2​,[m2​,a3​]=m3​,...,[mn−1​,an​]=mn​，那么有$[a_1,a_2,...,a_n]=m_n$[a1​,a2​,...,an​]=mn​

素数

定义4

素数任意一个大于1得正整数，正因数只有1和它本身，否则就叫做合数

性质2

$a\geq1$a≥1则除1之外的最小正因数q是素数，且当a是合数时，$q\leq \sqrt{a}$q≤a​
证明，$\color{blue}{反证法}$反证法
q不是素数，则存在因子$1<q_1\leq q$1<q1​≤q，与q是最小因子矛盾，故q是素数。
a=a₁q，$且q\leq a_1,故a\geq q^2$且q≤a1​,故a≥q2

定理10

素数的个数是无穷的

定理11

存在无数个形如4n-1的素数
证明：
补充：（4n+1）（4b-1）=4（4nb+b-n）-1，
奇数有两种4n+1和4n-1，任意多个4n+1的数或任意多个4n-1的数地乘积一定还是4n+1型的

定理12

证明：
若a₀=0 ，那么这个多项式不存在，因为它必是一个含有x₀作因子的合数
将a₀分解质因子为p₁,p₂…p_k，若x₀<其中最小的，不妨设为p₁，那么x取p₁就可以使这个式子变为合数。若x₀>其中最大的，那取x = a₀整数倍且>x₀，也可以使它变为合数

200以内素数

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113 127 131 137 139 149
151 157 163 167 173 179 181 191 193 197 199

定理13

如果$\pi(x)表示所有小于x的素数，则有\pi(x)\approx\frac{x}{ln x}$π(x)表示所有小于x的素数，则有π(x)≈lnxx​