定义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.2唯一分解定理

可行性：

当\(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.3

定义\(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\)进制下的进位个数

推论3.4

设正整数n的标准分解式为\(:n=p1^{e_1}p2^{e_2}...pk^{e_k}\)

设\(m=p1^{f_1}p2^{f_2}...pk^{f_k}\),则\(m|n\Rightarrow f_i<=e_i(1<=i<=k)\)

因数个数公式：

因数和公式：

因数积公式：