定义1.1整除
\(a\)整除\(b\)记为\(a|b\)
\(a|b\)指\(\exists n\in \mathbb{Z},使得b=an\)
定义1.2
-
1.整除的传递性：\(a|b,b|c\Rightarrow a|c\)
-
2.整除的可加性：\(n|a,n|b\Rightarrow n|a\pm b\)
-
3.整除的可乘性：\(a|b,c|d\Rightarrow ac|bd(a|b\Rightarrow a|bd)\)
eg1:
证明：如果\(3|x,7|x\Rightarrow 21|x\)
解：
\(21|x,21|3x\)
\(\therefore 21|7x-3x-3x\)
即\(21|x\)
eg2:
证明\(8|3^{2n+1}+5\)
解：
\(3^{2k+1}+5=3^{2k-1}-3+8=3 \times (3^{2k}-1)+8=3(9^k-1)+8=3 \times 8 \times (9^{k-1}+....+9+1)+8\)
定义2.1最大公因数
\(gcd(a,b):max\){\(m|m|a且m|b\)}
\(lcm(a,b):min\){\(n|a|n且b|n,n>0\)}
引理2.2带余除法
ps:2.2~2.7中(a,b)默认为gcd(a,b)
\(\forall a,b>0,\exists 唯一q,r使得
\begin{Bmatrix}
a=bq+r \\
0<=r<=b-1
\end{Bmatrix}\)
设\(r>=b\)
\(\therefore a-(k+1)b>=0\)
令\(r_1=a-(k+1)b\)
\(\therefore r_1<r,矛盾\)
\(\therefore\)存在一组\(q,r\)
下面证明\(q,r\)唯一
若\(a=bq_1+r=bq_2+r_2\)
\(\therefore \left | b(q1-q2) \right | =\left | r2-r1 \right |<=max(r2,r1)<=b-1\)
\(\because \left | b(q1-q2) \right | \mid b\)
\(\therefore q1-q2=0,q1=q2\)
\(\therefore q1=q2,r1=r2\)，矛盾。
\(q,r\)唯一。
定理2.3公倍数能被最小公倍数整除：
即证明：\(a|n,b|n\Rightarrow lcm(a,b)|n\)
解：
设\(n{\div} lcm(a,b)=q...r\)
\(\therefore n=qlcm(a,b)+r\)
\(a|n-qlcm(a,b)=r\)
同理，\(b|r\)
\(\therefore r\)也是\(a,b\)的公倍数
而\(0<=r<lcm(a,b)\),矛盾
引理2.4辗转相除法
若\(a{\div}b=q...r,则(a,b)=(b,r)\)
首先考虑如果\((a,b)=(a-b,b)\)，就可以通过多次相减把\((a,b)\)变成\((r,b)\)，下文证明：\((a,b)=(a-b,b)\)
\(\forall x \in a,b的公因数，有x|a,x|b\)
\(\therefore x|a-b\)
\(\therefore x \in a-b与b的公因数\)
\(a与b的公因数\subseteq a-b与b的公因数\)
同理可得：\(a-b与b的公因数\subseteq a与b的公因数\)
\(\therefore a与b的公因数= a-b与b的公因数\)
\(\therefore (a,b)=(a-b,b)\),得证
裴蜀定理
内容：
\(\forall a,b,\exists x,y使得ax+by=(a,b)\)
证明：
不妨令\(a>b\)
\(a_1=a,b_1=b,a1{\div} b_1=q_1....r_1\)
\(令a_2=b_1,b_2=a_1,a_2{\div } b_2=q_2....r_2\)
......
\(直到r_n=0时，(a_n,b_n)=b_n\)
\(\therefore (a,b)=a_nq_n\)
感性理解一下可以倒退回第一个式子。
其实只是作者太拉，不知道怎么形容
推论2.5
-
1.公因数整除最大公因数
-
2.整除的互质可消性
证明一下第2点，即证明：若\((a,b)=1,a|bc\)则\(a|c\)
由裴蜀定理得:\(\exists x,y使得ax+by=(a,b)\)
\(\therefore acx+bcy=c\)
\(\because a|bc\)
\(\therefore a|bcy\)
又\(\because a|acx\)
\(a|acx+bcy=c\)
性质2.6
-
\(1.(a,b,c)=((a,b),c)\)
-
\(2.(a,b)=(a,b,ax)\)
-
\(3.(a,b,c)=((a,b),(a,c))\)
例子2.7
eg1:
求证，已知a,b为正整数，\((2^{a-1},2^{b-1})=2^{(a,b)}-1\)
证明：
若\(a>b,(2^{a}-1-2^{a-b}(2^b-1),2^b-1))=(2^{a-b}-1,2^b-1)=2^{(a,b)}-1\)
eg2:
求证，已知\(a,b\)为正整数，\((2^{2^a}+1,2^{2^b}+1)=1\)
原式\(=(2^{2^a}-1+2,2^{2^b}+1)=((2^{2^{a-1} }+1 )(2^{2^{a-1} }-1)......(2^{2^{b} }+1)(2^{2^{b} }-1)+2,2^{2^{b} }+1)=(2,2^{2^{b} }+1)=1\)
定义3.1质数：
\(p>2,n|p\Rightarrow n=1或n=p\)
eg1:
证明存在无穷个质数
根据2.7eg2,\((2^{2^a}+1,2^{2^b}+1)=1\)
\(\therefore 2^{2^a}+1与2^{2^b}+1的质因子互不相同\)，得证
eg2:
证明若\(2^n-1\)为质数，\(n\)必为质数
设\(n=ab\)
根据2.7eg1,\((2^a-1,2^n-1)=2^{(a,n)}-1=2^a-1\)
\(\therefore 2^a-1|2^n-1\),矛盾，得证
定理3.4唯一分解定理
可行性：
当\(n=2\)时，可分解。
若\(n=2,3,....,k\)时均可分解，当\(n=k+1时\)
-
1.\(k+1\)时质数——自身就是分解
-
2.一定有\(k+1=ab\)，从\(a,b\)的分解推过来
唯一性：
设\(n=p_1p_2....p_s=q_1q_2....q_t(s>=t)\)
\(\because p_1|q_1q_2....\)
\(\therefore p_1|q_i,等价于p_1|q_1\)
由此可得\(p_{t+1}p_{t+2}....p_{s}=1\),矛盾，得证。
定义3.5
定义\(v_p(n):n\)的标准分解式中所含质因子\(p\)的指数
\(v_p(n1n2)=vp(n1)+vp(n2)\)
\(v_p(gcd(n1,n2))=min(v_p(n1),v_p(n2))\)
\(v_p(lcm(n1,n2))=max(v_p(n1),v_p(n2))\)
\(v_p(n!)=\sum_{i=1}^{\infty } \left \lfloor \frac{n}{p^i} \right \rfloor\)
\(v_p(C_{n}^{m})=\sum_{i=1}^{\infty } \left \lfloor \frac{n}{p^i} \right \rfloor-\left \lfloor \frac{m}{p^i} \right \rfloor-\left \lfloor \frac{n-m}{p^i} \right \rfloor\)
最下面式子的含义正好是\(n+(n-m)\)在\(p\)进制下的进位个数