定义1-1：设\(a,b(b\ne0)\)为整数，如果存在整数\(c\)，使得\(a=bc\)成立，则称\(b\)整除\(a\)，记为\(b\mid a\)。否则称\(b\)不整除\(a\)，记为\(b\nmid a\)。如果\(b\mid a\)，则称\(b\)为\(a\)的因子，\(a\)为\(b\)的倍数。
特殊的，我们将能够被2整除的整数称为偶数，否则称为奇数。通过上述定义可知，对于任意不等于零的整数均整除零。
以下是整除的简单性质，可以很容易被验证：
例题：证明 \(6|n(n+1)(n+2),n\in N^*\)
这里采用数学归纳法进行证明，可以验证当\(n=1\)的时候，上述式子成立。这里假设\(n=k\)的时候，上述整除式子成立，即\(6|k(k+1)(k+2)\)成立，对于\(n=k+1\)的情况如下：
\[
(k+1)(k+2)(k+3)=k(k+1)(k+2)+3(k+1)(k+2)
\]
因为连续两个正整数的乘积必然是偶数，即\(2|(k+1)(k+2)\)，因此有
\[
6\mid{[k(k+1)(k+2)+3(k+1)(k+2)]}
\]
综上可知，原命题成立。
定理1-1：设\(a,b\)是两个整数，且\(b\ne0\)，则存在唯一的两个整数\(q,r\)，使得\(a=bq+r,0\le r<|b|\)成立。
我们将\(q\)称为\(a\)被\(b\)除所得的商，\(r\)称为\(a\)被\(b\)除所得的余数。
可以将上述定理可以写成：\(a\div b=q\cdots r\)的形式，这种形式称为带余除法。
存在性证明：
对于\(b<0\)的情况，无非是将第二步的不等关系更换为：\(qb\le a<(q-1)b\)
唯一性证明：
假设存在两组不同的整数\(q_1,r_1\)和\(q_2,r_2\)，使得
\[
a=q_1b+r_1=q_2b+r_2
\]
因此
\[
|q_1-q_2||b|=|r_1-r_2|
\]
又因为\(0\le r_1,r_2<|b|\)，所以\(|r_1-r_2|<|b|\)，因此\(0\le|q_1-q_2|<1\)。
因为\(|q_1-q_2|\)必须是整数，所以\(q_1=q_2\)，于是也有\(r_1=r_2\)。
定义1-2：若\(d|a_1,d|a_2\)，则称\(d\)是\(a_1,a_2\)的一个公因子。其中绝对值最大的公因子，称为最大公因子，记作\((a_1,a_2)\)。
例如，2和4的公因子有：\(\pm1,\pm2\)，其中最大公因子为2。
需要注意的是，如果\(a=b=0\)，这种情况下，是没有最大公因子的。
定义1-3：如果\((a_1,a_2)=1\)，则称\(a_1,a_2\)互素。
定理1-2：设\(a,b,c\in Z\)，如果\(a=bq+r,b\ne0\)，那么\((a,b)=(b,r)\)。
上述定理是辗转相除法的基础，证明如下：
通过带余除法可以得到：\(a=qb+r\Leftrightarrow r=a-qb\)
假设\(a,b\)公因子所构成的集合为\(D_1\)；\(b,r\)公因子所构成的集合为\(D_2\)
综上可知，\(D_1=D_2\)，因此\((a,b)=(b,r)\)。
辗转相除法：计算正整数\(a,b\)的最大公因子\((a,b)\)
\[
a=bq_0+r_0\rightarrow(a,b)=(b,r_0)\b=r_0q_1+r_1\rightarrow(b,r_0)=(r_0,r_1)\r_0=r_1q_2+r_2\rightarrow(r_0,r_1)=(r_1,r_2)\\vdots\r_{n-2}=r_{n-1}q_{n}+r_n\rightarrow(r_{n-2},r_{n-1})=(r_{n-1},r_n)\r_{n-1}=r_nq_{n+1}\rightarrow(r_{n-1},r_n)=r_n\\]
带余除法的性质可以保证每经过一次运算就可以使得余数\(r_i\)减小，因此经过有限步骤运算之后，必然出现余数为零的情况，此时说明我们已经求得最大公因子，并且最大公因子为\((a,b)=r_n\)。
需要注意的是，对于\(a,b\)中出现负数的情况，直接使用辗转相除法，可能出现\(r_n\)是负数的情况。例如，\(-4=(-2)\times2\)。因此，返回的最大公因子应该是\(|r_n|\)。
并且根据辗转相除法的计算过程，我们还可以得到一个有用的结论。对于任意\(r_{i-2}=r_{i-1}q_{i}+r_i\)而言，我们都可以利用迭代过程中计算的中间结果，通过回代的方式消去\(r_{i-2},r_{i-1}\)，最终可以得到\(r_i=sa+tb\)的形式，其中\(s,t\in Z\)。对于最大公因子而言，我们可以得到下述定理1-3。
定理1-3：对于\(ab\ne0\)，存在整数\(s,t\)，使得\((a,b)=sa+tb\)。
上述定理1-3，对于\(a,b\)的正负性没有要求。事实上对于\(a=0,b\ne0\)或\(b=0,a\ne0\)的情况，定理1-3也是成立的。因为根据整除的定义，以及最大公因子的定义可以得到\((a,0)=|a|\)。但是如果将这种情况，考虑到辗转相除法当中，可能会出现错误，因为对于\(2=0\times q+r\)成立而言，只可能是\(r=2\)，这显然不满足带余除法的定义。
定理1-3的推论：设\(a,b\in Z\),则\(a,b\)互素的充要条件是\(\exists m,n\in Z,\;ma+nb=1\)。
显然当\(a,b\)互素时，条件成立。当该条件成立时，如果\(a,b\)仍然有大于1的公因子，不妨设为\(d\)，那么
\[
m\frac{a}d+n\frac{b}d=\frac{1}d
\]
显然等式左侧是整数，右侧是小数，因此\(d=1\)。
定理1-4：对于\(ab\ne0,m\ne0\)
\((am,bm)=|m|(a,b)\)
\(a,b\)的任意公因子\(h\)，都有\(h|(a,b)\)成立
若\(d|a,d|b\)，则
\[
(\frac{a}d,\frac{b}d)=\frac{(a,b)}{|d|}
\]
特别地，当\(d=(a,b)\)时，有
\[
(\frac{a}d,\frac{b}d)=1
\]
证明：
令\(a=a'(a,b),b=b'(a,b)\)，则\((a',b')=1\)。因为如果\((a',b')>1\)说明\(a',b'\)还有大于1的公因子，因此\((a,b)\)就不是最大公因子，这和最大公因子的定义矛盾，因此\((a',b')=1\)必然成立。
\(am=a'm(a,b),bm=b'm(a,b)\)，显然\((am,bm)=|m|(a,b)\)
因为存在\(s,t\)，使得\((a,b)=sa+tb\)。如果\(h|a,h|b\)，那么\(h|(sa+tb)\)，即\(h|(a,b)\)
如果\(d|a,d|b\)，利用结论2可知\(d|(a,b)\)。结合结论1，可以得到
\[
(a'\frac{(a,b)}d,b'\frac{(a,b)}d)=\frac{(a,b)}{|d|}
\]
定理1-5：对于\(ab\ne0,m\ne0\)
\((a,m)=1,(a,b)=1\)（互素），那么\((a,bm)=1\).
利用定理1-3的推论即可证明：
\[
\exists s,t\in Z,\;as+mt=1\\exists p,q\in Z,\;ap+bq=1\(as+mt)(ap+bq)=1\Rightarrow a(\cdots)+bm(qt)=1
\]
\(a,m\)互素，则\(m|ab\Rightarrow m|b\)
\[
\begin{aligned}
\exists s,t\in Z,\;as+mt=1
\Rightarrow abs+mbt=b\\end{aligned}
\]
这个性质在化简同余式的时候，挺有用的。需要注意的是，\(m|b\Rightarrow m|ab\)是一定成立的。
\(a|m,b|m\)，且\((a,b)=1\)，则\(ab|m\)
因为存在整数\(s,t\)使得，\(m=sa=tb\)成立。并且\((a,b)=1,a|tb\)，所以利用上述结论2可得\(a|t\)，因此我们有\(t=ka,m=tb=kab\)，所以\(ab|m\)。
定义1-4：若\(d|a_1,d|a_2,\cdots,d|a_n,n\ge2\)，则称\(d\)是\(a_1,a_2,\cdots,a_n\)的一个公因子，其中最大的称为最大公因子，记为\((a_1,a_2,\cdots,a_n)\)。
如果\((a_1,a_2,\cdots,a_n)=1\)，则称\(a_1,a_2,\cdots,a_n\)互素。如果任意两个都互素，则称\(a_1,a_2,\cdots,a_n\)两两互素。
定理1-6：\((a_1,a_2,\cdots,a_n)=((a_1,a_2,\cdots,a_{n-1}),a_n)\)
证明：令\((a_1,a_2,\cdots,a_n)=d\)，\((a_1,a_2,\cdots,a_{n-1})=d_{n-1}\)，\((d_{n-1},a_n)=d_n\)
首先，利用定理1-4中的结论2可以证明\(d|d_n\)
\[
\begin{aligned}
&(a_1,a_2,\cdots,a_n)=d\\Rightarrow&\;\;d|a_1,d|a_2,\cdots,d|a_n\\Rightarrow&\;\;d|d_{n-1}\\Rightarrow&\;\;d|d_{n}
\end{aligned}
\]
同理，可证明\(d_n|d\)
\[
\begin{aligned}
&(d_{n-1},a_n)=d_n\\Rightarrow&\;\;d_n|a_n,d_n|d_{n-1}\\Rightarrow&\;\;d_n|a_1,d_n|a_2,\cdots,d_n|a_n\\Rightarrow&\;\;d_{n}|d
\end{aligned}
\]
因为\(d_n>0,d>0\)，所以\(d=d_n\)。
通过定理1-6，我们就可以逐步求解多个数的最大公倍数。
定义1-5：整数\(a_1,a_2,\cdots,a_n\)的公共倍数称为\(a_1,a_2,\cdots,a_n\)的公倍数，其中最小的正公倍数称为最小公倍数，记为\([a_1,a_2,\cdots,a_n]\)。
最小公倍数有如下性质，可以很容易被验证：
定理1-7：对于任意的正整数\(a,b\)有
证明：假设\(a,b\)的某一个公倍数为M，那么存在整数\(s,t\)使得\(M=sa=tb\)。同时令\(a=a'(a,b),b=b'(a,b)\)，那么\((a',b')=1\)。
\[
M=sa'(a,b)=tb'(a,b)\Rightarrow sa'=tb'
\]
因为\(a'|tb',(a',b')=1\)，所以\(a'|t\)，因此存在整数\(k\)，使得\(t=ka'\)，于是我们得到
\[
M=ka'b'(a,b)=k\frac{ab}{(a,b)}
\]
当\(k=1\)时，\(M\)有最小值，此时\([a,b]=ab/(a,b)\)；并且公倍数\(M\)一定是最小公倍数的倍数。对于结论3有
\[
[ma,mb]=\frac{m^2ab}{(ma,mb)}=\frac{m^2ab}{m(a,b)}=m\frac{ab}{(a,b)}=m[a,b]
\]
定理1-8：\([a_1,a_2,\cdots,a_n]=[[a_1,a_2,\cdots,a_{n-1}],a_n]\)
证明：证明思路和多个数的最大公因子类似
令\([a_1,a_2,\cdots,a_n]=m\)，\([a_1,a_2,\cdots,a_{n-1}]=m_{n-1}\)，\([m_{n-1},a_n]=m_n\)
首先，证明\(m_n|m\)：
\[
\begin{aligned}
&[a_1,a_2,\cdots,a_n]=m\\Rightarrow\quad&a_1|m,a_2|m,\cdots,a_n|m\\Rightarrow\quad&m_{n-1}|m\\Rightarrow\quad&m_n|m
\end{aligned}
\]
其次，证明\(m|m_n\)：
\[
\begin{aligned}
&[m_{n-1},a_n]=m_n\\Rightarrow\quad&m_{n-1}|m_n,a_n|m_n\\Rightarrow\quad&a_1|m_n,a_2|m_n,\cdots,a_{n-1}|m_n\\Rightarrow\quad&m|m_n
\end{aligned}
\]
所以\(m=m_n\)成立。
定义1-6：若整数\(p>1\)，并且它的因子只有\(\pm1,\pm p\)，那么称\(p\)是素数，否则称为合数。
素数的基本性质：
若\(p\)为素数，那么对于任意整数\(n\)而言，\(p|n\)和\((p,n)=1\)有且仅有一个成立。
因为素数\(p\)的正因子只有\(1,p\)，那么\((p,n)=1\)或\((p,n)=p\)有且仅有一个成立。当\((p,n)=p\)时，说明\(p|n\)。
如果\(n\ge2\)，则必存在合数\(n\)，使得\(p|n\)，并且\(p\le\sqrt{n}\)。
如果\(n\)是合数，那么就可以进行分解，例如，\(n=xy\)，其中\(1<x,y<n,x\le y\)。通过这样不断分解，最终就可以找到比\(n\)小的素数。并且合数分解的时候，必然满足\(x\le\sqrt{n},y\ge\sqrt{n}\)，因此\(p\le\sqrt{n}\)成立。
如果\(p|mn\)，那么\(p|m\)或\(p|n\)。推广到有限个整数则有，若\(p|a_1a_2\cdots a_n\)，那么\(p|a_1\)，\(p|a_2,\cdots,p|a_n\)有且只有一个成立。
定理1-9：素数有无穷多个，并且当\(n\)很大的时候，不超过\(n\)的素数个数近似为\(n/\log n\)。
该定理的前一部分，早已被欧几里得证明，后一部分实际上指的是素数定理。
补充定理1：设\(n>1\)，若\(a^n-1(a\ge2)\)是素数，则\(a=2\)，且\(n\)为素数。
证明：
定义：整数\(M_n=2^n-1\)称为第n个Mersenne数，当\(M_n\)是素数的时候，称\(M_n\)为Mersenne素数。
梅森素数实例：\(3=2^2-1,31=2^5-1\)
梅森素数的应用：将除法转换成加法
假设有梅森素数\(q=2^p-1\)，计算整数C除以q余数，将整数C表示为
\[
C=C_0+2^pC_1=C_0+C_1+(2^p-1)C_1,\; C_0<2^p
\]
此时C除以q的余数与\(C_0+C_1\)除以q的余数相同。
准梅森素数：形如\(p=2^n-a\)（其中\(a\)是一个很小的整数）的素数。同样的可以利用准梅森素数将除法转换成加法，只需计算\(C_0+aC_1\)除以\(p\)的余数即可。
补充定理2：若\(2^m+1\)为素数，那么\(m\)一定是2的方幂。
证明：假设m有一个奇数因子\(n\)，且\(m=nk\)，那么
\[
\begin{aligned}
2^m+1&=(2^{k})^n+1\&=(2^k+1)((2^k)^{n-1}-(2^k)^{n-2}+\cdots+1)
\end{aligned}
\]
此时，\(1<2^k+1<2^m+1\)，所以\(2^m+1\)不可能是素数。因此，m不可能含有奇数因子。
费马素数：形如\(F_n=2^{2^n}\)的数称为费马数，若\(F_n\)为素数，则称为费马素数。
可以验证\(F_1,F_2,F_3,F_4\)均是素数，但\(F_5\)不是素数（由欧拉验证），欧拉分解\(F_5\)的方法如下：
如果\((a,b)=1\)，那么
通过穷举的方式，可以发现\(F_5=2^{32}+1\)具有素因子\(641=64\times10+1\)
筛选法可以用来找小于等于n的素数，筛选步骤如下：
定理1-10：【算数基本定理】任意一个大于1的整数能够唯一表示成素数的乘积，即对于\(n>1\)，有
\[
n=p_1p_2\cdots p_m,\;p_1\le p_2\le\cdots\le p_m
\]
将相同的素因子写成幂的形式，得到整数的标准分解式：\(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}, p_i<p_j(i<j)\)。
存在性证明：如果n本身即是素数，那么命题成立。如果n是合数，那么就可以将n进行分解成n的真因子乘积的形式，如果n的真因子仍然是合数，那么就对其继续分解，最后必然分解成素数乘积的形式，此时只需将素数从小到大排列即可。
唯一性证明：假设n可以分解成两种不同的形式（素数从小到大排列）
\[
n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
=q_1^{\beta_1}q_2^{\beta_2}\cdots q_l^{\beta_l}
\]
首先证明\(l=k\)并且\(p_i=q_i(i=1,2,\cdots,k)\)：
因为\(p_i|n\)，所以\(p_i|q_1^{\beta_1}q_2^{\beta_2}\cdots q_l^{\beta_l}\)，所以\(l\ge k\)，即第一中分解形式中的所有素数均在第二种分解形式中出现；同理可得\(k\ge l\)，因此\(l=k\)，并且\(p_i=q_i(i=1,2,\cdots,k)\)。
其次证明\(\alpha_i=\beta_i(i=1,2,\cdots,k)\)：
不妨假设\(\alpha_i>\beta_i\)，此时有\(p_i^{\alpha_i}|n\)，\(p_i^{\alpha_i}\nmid{q_1^{\beta_1}q_2^{\beta_2}\cdots q_l^{\beta_l}}\)，相矛盾。因此，必然有\(\alpha_i=\beta_i(i=1,2,\cdots,k)\)。
定理1-11：对于任意两个正整数\(a,b\)，利用算术基本定理，将其分解成素数乘积的形式：
\[
a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\b=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}\\alpha_i,\beta_i\ge0,\;i=1,2,\cdots,k
\]
有如下结论成立：
\[
(a,b)=p_1^{\gamma_1}p_2^{\gamma_2}\cdots p_k^{\gamma_k},
\;\gamma_i=\min\{\alpha_i,\beta_i\}\\{}
[a,b]=p_1^{\delta_1}p_2^{\delta_2}\cdots p_k^{\delta_k},
\;\delta_i=\max\{\alpha_i,\beta_i\}\i=1,2,\cdots,k
\]
例子：
\[
a=2^3\times3^2\times5\b=2^2\times3\times5^2\(a,b)=2^2\times3\times5=60\\lbrack a,b\rbrack=2^3\times3^2\times5^2=1800
\]
原文：https://www.cnblogs.com/philolif/p/12163854.html