本文主要阐述整除及其性质，介绍素数与合数，最大公因数与最小公倍数，配合B站相应视频，兼顾到OI和数学专业书籍知识点的平衡，在尽量保证知识体系完整的情况下内容尽量精简。
讲义写完后感觉费时费神而且照着讲义讲也没多大意义，下次可能不会再写那么详细的了。
相应习题解答在参考文献上都有请自行查阅。
整除的定义和性质
整除
定义：设a,b \in \mathbb{Z} ,a \not= 0，如果存在q \in \mathbb{Z}使得b = aq，那么就说b可被a整除（a整除b），记作a \mid b，称a是b的倍数，b是a的因数（除数、约数）。反之，b不能被a整除记作a \nmid b。
性质与定理
以下是整除的基本性质：
(i) a \mid b, \; b \mid c \implies a \mid c
(ii) a \mid b, \; a \mid c \iff \forall x,y \in \mathbb{Z}, \; a \mid bx+cy
一般地，a \mid b_{1}, \cdots ,a \mid b_{k} \iff \forall x_{1}, \cdots ,x_{k} \in \mathbb{Z} , \; a \mid b_{1} x_{1} + \cdots + b_{k} x_{k}
(iii) 设a \not= 0, \; b=qa+c，则a \mid b \iff a \mid c
证明：
(i) b=au, \; c=bv \implies c=auv \implies a \mid c
(ii)
(必要性)
b=aq_{1}, c=aq_{2} \implies bx+cy=a(bq_{1}+cq_{2})
(充分性)
分别取x=0,y=1与x=1,y=0即可。
一般性结论的证明留作习题。
(iii)
(充分性)c=at \implies b=a(q+t)
(必要性)c=b-qa, \; b=at \implies c = a(t-q)
例题
例：若3 \mid n且7 \mid n则21 \mid n。
证明：
由题n=3m故7 \mid 3m，再由7 \mid 7m可得7 \mid (7m-2 \cdot 3m)=m得证。
素数与合数
素数
定义：设整数p \not=0, \pm 1，如果除了\pm 1,\pm p以外没有其它约数，就称为不可约数，又叫素数（质数），反之称为合数。
约定：没有特别说明时素数p总是指正整数。
例如：2,3,5,7,11,13,19260817,2147483647均为质数
性质与定理
以下是有关素数的部分性质：
(i) 若d \geq 2，p是素数且d \mid p，则d=p
(ii) （算术基本定理或唯一分解定理）设整数a \geq 2，则\exist p_{1} \cdots p_{k}是素数，使得
a= \prod_{i=1}^{k} p_{i}。在不考虑p_{i}次序的情况下，这样的分解是唯一的。
证明：
(i) 显然。
(ii) 唯一性暂不作证明，存在性用数学归纳法（书上使用了更基本的最小自然数原理进行证明，但不够直观，有兴趣的可以看看）：
当a=2时，显然取素数2即可。
若a \geq 3，归纳假设对小于a的数均存在质因数分解，即从2开始直到a-1，均有相应质因数分解。我们考虑a是否能被2到a-1的某个数k整除，若可以则得到分解a=mk，再将k分解为相应质因数乘积，此时显然满足m \leq a，再对m进行相应分解。若均不能整除，则a一定为素数，分解即为自身。
(ii)的推论（自证）：
若a \geq 2，
(i) 若a是合数，则必有素数p \mid a且p \leq \sqrt{a}；（该性质保证了埃式筛的正确性）
(ii) 若a有质因数分解a= \prod_{i=1}^{k} p_{i}，则必有素数p \mid a, \; p \leq \sqrt[k]{a}
互素
互素的定义
定义：若(a_{1}, \cdots ,a_{n})=1，则称这些数是互素的（既约的）。
互素的性质
(i) Bezout等式：(a_{1}, \cdots ,a_{n})=1 \iff \exist x_{1}, \cdots ,x_{n}, \; \sum_{i=1}^{n} a_{i}x_{i}=1
(ii) 设正整数m \mid (a_{1}, \cdots ,a_{n})，则m(a_{1}/m, \cdots ,a_{n}/m)=(a_{1}, \cdots ,a_{n})。特别地(\frac{a_{1}}{(a_{1}, \cdots ,a_{n})}, \cdots ,\frac{a_{n}}{(a_{1}, \cdots ,a_{n})})=1
证明：(i)暂不作证明。
(ii)
取1 \leq j \leq k记D=(a_{1} /m, \cdots ,a_{n}/k)，由m \mid D, D \mid a_{j} \implies m \mid a_{j},
因此(D/m) \mid (a_{j}/m)
故D/m为a_{j}/m的正公约数，则D/m \leq (a_{1}/m, \cdots ,a_{k}/m)。
另一方面，若有d \mid (a_{j}/m)，则md \mid a_{j}，故md \leq D，取d=(a_{1}/m, \cdots ,a_{k}/m)即可。
最大公约数与最小公倍数
最大公约数
定义：若a_{1}, \cdots ,a_{n}是整数，另有整数d满足d \mid a_{1}, \cdots ,d \mid a_{n}则称d为a_{1}, \cdots ,a_{n}的公约数。记a_{1}, \cdots ,a_{n}的公约数构成的集合\mathcal{D}(a_{1}, \cdots ,a_{n})，其中最大的一个称为最大公约数，记为(a_{1}, \cdots ,a_{n})。
最大公约数的性质
最大公约数具有如下性质：
(i) 若a_{1} \mid a_{j}(j=2, \cdots ,n)，则(a_{1},a_{2})=(a_{1}, \cdots ,a_{n}) = (a_{1}) = \vert a_{1} \vert
(ii) \forall x, \; (a_{1}, \cdots ,a_{n}) = (a_{1}, \cdots ,a_{n}, xa_{j})(j \in {1, \cdots ,n})
(iii) \forall x, (a_{1}, \cdots ,a_{j}, \cdots ,a_{n})=(a_{1}, \cdots ,a_{j}+xa_{k}, \cdots ,a_{n})(j,k \in{1, \cdots ,n})
以上性质证明留作习题。
最小公倍数
定义：设a_{1}, \cdots ,a_{n}均不为0，若\exist l,a_{1} \mid l, \cdots ,a_{n} \mid l，则称l为a_{1}, \cdots ,a_{n}的公倍数。记a_{1}, \cdots ,a_{n}的公倍数集合为\mathcal{L}(a_{1}, \cdots ,a_{n} )，其中最小的一个称为最小公倍数，记为[a_{1}, \cdots ,a_{n}]。
最小公倍数的性质
最小公倍数具有如下性质：
(i) 若a_{j} \mid a_{1}(j=2, \cdots ,k)，则[a_{1}, \cdots ,a_{n}]=a_{1}
(ii) \forall d \mid a_{1}，[a_{1}, \cdots ,a_{n}]=[a_{1}, \cdots ,a_{n},d]
(iii) 若m \not=0则[ma_{1}, \cdots ,ma_{n}]=m[a_{1}, \cdots ,a_{n}]
证明：(i)和(ii)证明留作习题。
(iii)
设L=[ma_{1}, \cdots ,ma_{n}], \; L'= [a_{1}, \cdots ,a_{n}]，对1 \leq j \leq n，ma_{j} \mid L \implies a_{j} \mid \frac{L}{m}（注意到\frac{L}{m}是整数）（即\frac{L}{m}是a_{1}, \cdots ,a_{n}的公倍数），故L' \leq \frac{L}{m}。另外由a_{j} \mid L' \implies ma_{j} \mid mL'（即mL'是ma_{1}, \cdots ,ma_{n}的公倍数），故L \leq mL'，由此L=mL'
例题
问题：求(30,45,84)。
解：(30,45,84)=(30,15,84)=(0,15,84)=(15,84)=(15,-6)=(3,-6)=3
习题
证明：设a,b \in \mathbb{N}_{+}, \; \exist x,y \in \mathbb{Z}使得ax+by=1，若a \mid n, \; b \mid n则ab \mid n。
证明：一个正整数各位数字之和能被3整除，则这个正整数能被3整除。（该性质同样适用于6和9）
证明：素数有无穷多个。（提示：可以用反证法）
问题：有一种盒子能装3斤糖，另一种能装6斤糖，是否能够选择合适的不同盒子个数，使得每个盒子装满情况下装了100斤糖？
证明：若n \not= 1，则(n-1)^{2} \mid n^{k}-1 \iff (n-1) \mid k。（提示：需要用到因式分解）
证明：设n \geq 1
(i) 2^{n}+1是质数的必要条件是n=2^{k}。
(ii) 2^{n}-1是质数的必要条件是设n为质数。
（提示：需要用到因式分解）
证明：设n^{2}+n+41当0 \leq n \leq 39时都是素数。
证明：设q \not= 0, \pm 1，若对任意a,b，由q \mid ab，一定有q \mid a或q \mid b，则q一定是不可约数。（提示：可否定其中一个结论证明另一个）
证明：设a,b,n满足a \mid bn, \; ax+by=1，则a \mid n。
问题：任意正整数n，求下列最大公约数：
(i) (21n+4,14n+3)；
(ii) (2n-1,n-2)；
(iii) (n-1, n^{2}+n+1)。
证明：若a,b满足ax+by=1，则：
(i) [a,b]=ab；
(ii) (ac,b)=(c,b)。
证明：记\varphi (n)(n \geq 1)为1, \cdots, n中与n既约的个数，则：
(i) \varphi (1)= \varphi (2) = 1；
(ii) n \geq 3则2 \mid \varphi (n)；
(iii) 当n为素数时，\varphi (n)=n-1。
参考文献：
[1]潘承洞, 潘承彪.初等数论（第三版）[M]. 北京:北京大学出版社, 2013. 8-22.