本节的目的是简述整数的初等可除性质，以便在后面的章节中引用.进一步的结果将在第$5$章给出，在那里，整除性理论被推广到更一般的代数系统中.

算术基本定理

若存在某个$t\in \mathbb{Z} $，使得$n=st$，则整数$s$叫作整数$n$的因数(或因子)，$n$本身叫作$s$的倍数.$n$被$s$整除记作$s\mid n$，而$n$不能被$s$整除记作$s\nmid n$.整除性是$\mathbb{Z} $上的传递关系.如果$m\mid n$且$n\mid m$，则$n=\pm m$，而整数$n,m$叫作相伴的.如果整数$p$的全部因子为$\pm p$，$\pm 1$(非真因子)，则称$p$为素数.通常约定素数是正的且大于$1$.

下述定理表现出素数的基础作用.

算术基本定理 每一个正整数$n\neq 1$都可以分解成素数的乘积$n=p_1 p_2 \cdots p_s $.这一写法除因子的次序外是唯一的.

将相同因子收集到一起并改变记法，我们得到

$$ n=p_1^{\varepsilon _1 } p_2^{\varepsilon _2 } \cdots p_k^{\varepsilon _k } ,\quad \varepsilon _i > 0 ,1\leq i\leq k.$$

任意有理数$a=\dfrac{n}{m} \in \mathbb{Q} $也有类似的分解，但指数$\varepsilon _i $有正数也有负数.

我们指出，全体素数的集合

$$P=\lbrace 2,3,5,7,11,13,\cdots \rbrace $$

是无限集(欧几里得定理).事实上，如果仅有有限个素数，设为$p_1 ,p_2 ,\cdots ,p_t $，那么根据基本定理，整数$c=p_1 p_2 \cdots p_t +1$至少被某一个$p_i $除尽.不失一般性，设$c=p_1 c’$.则$p_1 (c’-p_2 \cdots p_t )=1$，这是不可能的，因为单位元在$\mathbb{Z} $中的因子只有$\pm 1$.$\quad \quad\quad \square$

基本定理的证明将延迟至第$5$章给出.一眼看来，定理似乎是显然的，以至不需要证明.但事实并非如此，尽管所谈问题仅涉及整数乘法的性质(整除性)，基本定理的证明却必须同时用到$\mathbb{Z} $中的乘法和加法运算.

为了说明定理的非平凡性，考察$\mathbb{N} $中的子集

$$S=\lbrace 4k+1 \mid k=0,1,2,\cdots \rbrace .$$

$S$关于乘法封闭：

$$(4k_1 +1)(4k_2 +1)=4k_3 +1.$$

对$n\in S$作归纳不难证明分解的存在性(类似于基本定理的第一部分)，即$n$可以分解成：$n=q_1 \cdots q_t $，其中$q_i $不能用$S$中的元素做进一步分解.称之为拟素数.$5,9,13,17,21,49$都是这种拟素数的例子.

基本定理的第二部分对$S$不真，例如数$441\in S$就有两种不同的到拟素数的分解：$441=9\cdot 49 ={21}^2$.

$\mathbb{Z} $中的最大公约数和最小公倍数

如果允许使用零方幂(永远认为$p_i^0 =1$)，任意两个整数$n$和$m$都可以写成同一组两两不等的素数方幂的乘积：

$$ n=\pm p_1^{\alpha _1 } p_2^{\alpha _2 } \cdots p_k^{\alpha _k } ,m=\pm p_1^{\beta _1 } p_2^{\beta _2 } \cdots p_k^{\beta _k } .$$

引入两个整数

$$\begin{matrix} g.c.d(n,m)=p_1^{\gamma _1 } p_2^{\gamma _2 } \cdots p_k^{\gamma _k }, \\ l.c.m(n,m)=p_1^{\delta _1 } p_2^{\delta _2 } \cdots p_k^{\delta _k }, \\ \end{matrix} \label{1} \tag{1}$$

其中$\gamma _i =\min \lbrace \alpha _i ,\beta _i \rbrace $，$\delta _i =\max \lbrace \alpha _i ,\beta _i \rbrace $，$i=1,2,\cdots ,k$.

因为$d\mid n \Rightarrow d=\pm p_1^{\alpha’ _1 } \cdots p_k^{\alpha’ _k },0\leq \alpha’ _i \leq \alpha _i $，所以从$\eqref{1} $式可得下述论断.

$i) \\ g.c.d(n,m)\mid n ,g.c.d(n,m)\mid m$，并且若$d\mid n,d\mid m$，则$d\mid g.c.d(n,m)$.

$ii) \\ n\mid l.c.m(n,m) ,m\mid l.c.m(n,m)$，并且若$n\mid u,m\mid u$，则$l.c.m(n,m)\mid u$.

性质$i)$和$ii)$证实了记号$g.c.d$和$l.c.m$分别是整数$n,m$的最大公因数和最小公倍数.当$n > 0,m > 0$时，它们满足关系

$$g.c.d(n,m)\cdot l.c.m(n,m)=nm.\label{2} \tag{2} $$

若$g.c.d(n,m)=1$，则称整数$n,m$为互素的.这时$\eqref{2} $式具有形式$l.c.m(n,m)=nm$.

$\mathbb{Z} $中的带余除法

给定$a,b\in \mathbb{Z} ,b > 0$，总可以找到$q,r \in \mathbb{Z} $，使得

$$a=bq+r ,\quad 0\leq r < b$$

(如果仅仅假设$b\neq 0$，那么有不等式$0\leq r < \mid b\mid $).

证明 事实上，集合

$$S=\lbrace a-bs\mid s\in \mathbb{Z} ,a-bs \geq 0\rbrace $$

显然不空(例如$a-b(-a^2) > 0$).于是$S$包含一个最小元素，记作$r=a-bq$.根据条件，$r\geq 0$.假如$r \geq b$，我们得到元素$r-b=a-b(q+1)\in S$，它小于$r$.这一矛盾说明，$r$必须小于$b$.

上述简单的论证给出了一个算法，可以通过有限步找到商数$q$和余数$r$，$\mathbb{Z} $中的带余除法可以用来给出$g.c.d$的另一种定义，如果注意到关系式$\eqref{2} $，还有$l.c.m$的另一种定义.

作法如下，给定不全为零的整数$n$和$m$，令

$$J=\lbrace nu+mv\mid u,v\in \mathbb{Z} \rbrace \label{3} \tag{3} $$

选出$J$中的最小正数$d=nu_0 +mv_0$.运用带余除法将$n$写作$n=dq+r,0\leq r < d$.我们有

$$r=n-dq=n-(nu_0 +mv_0 )q=n(1-u_0 q)+m(-v_0 q)\in J,$$

从$d$的选取得到$r=0$.因而$d\mid n$.类似地，$d\mid m$.现在假设$d’$是数$n$和$m$的任意一个公因子.这时

$$d’\mid n,d’\mid m\Rightarrow d’\mid nu_0 ,d’\mid mv_0 \Rightarrow d’\mid (nu_0 +mv_0 )\Rightarrow d’\mid d.$$

这样$d$具备最大公因数的一切性质，所以$d=g.c.d(n,m)$.我们证明了下述论断.

命题 两个不全为零的整数的最大公因数总可以写成下述形式：

$$g.c.d(n,m)=nu+mv ,\quad u,v\in \mathbb{Z} \label{4} \tag{4} $$

特别地，整数$n,m$互素，当且仅当存在某对$u,v\in \mathbb{Z} $，使得

$$nu+mv=1. \label{41} \tag{4′} $$

证明 我们已经验证过，互素的整数$n,m$满足关系式$\eqref{41} $.反之，如果$n,m$满足$\eqref{41} $，则

$$d\mid n,d\mid m\Rightarrow d\mid nu,d\mid mv\Rightarrow d\mid (nu+mv)\Rightarrow d\mid 1\Rightarrow d=\pm 1. \quad \quad \square $$

关系式$\eqref{4} $和$\eqref{41} $的证明是非常有用的.只需从集合$J$中取出任意一个正数(见$\eqref{3} $式)，然后借助带余除法找到$J$中越来越小的正数，直到得出最小的正数，这就是最大公因数.

习题

$1$.每一个不等于$2$的素数都可以写成$4k+1$或$4k-1$的形式.运用在第$1$段给出的集合$S$的乘法证明，形如$4k-1$的素数有无穷多个.

证明：假设形如$4k-1$的素数是有限的，$p$是其中最大的一个数.令

$$N=2^2\cdot 3\cdot 5\cdots p-1,$$

显然$N$是$4k-1$型的，并且$N > p$，根据假设知素数是有限的，且$p$最大的，故其余剩下的数，如$N$就应该是一个合数.

由于$2,3,5,\cdots ,p$均不是$N$的因数，所以$N$的所有素因数应该都大于$p$的.

因为$N$的因数有以下四种：$4k$，$4k+1$，$4k+2$，$4k+3$，其中$4k$与$4k+2$不是素数，所以$N$的素因数只能是$4k+1$与$4k+3$这两类.

因为$(4a+1)(4b+1)=4(4ab+a+b)+1$，知两个$4k+1$型的数相乘还是$4k+1$型的数，但是$N$是$4k-1$型（即$4k+3$型）的，所以$N$至少有一个$4k+3$型的素因数，记为$q$，$q$却大于$p$，即与假设产生矛盾.故假设不成立，即形如$4k-1$的素数有无穷多个.

$2$.下述论断是非平凡的.

若$n,m\in \mathbb{Z} ,g.c.d(n,m)=1$,如果$p$是整除$n^2+m^2$的一个素数，则$p=4k+1$.

试用该论断证明存在无穷多个形如$4k+1$的素数.

证明：事实上可以转化证明：存在无穷多个形如$8k+5$的素数.

假设形如$8k+5$的素数是有限的，$p$是其中最大的一个数.令

$$q=3^25^27^2\cdots p^2 +2^2,$$

这是两个没有公约数的平方数之和.又因为$3\times 5\times \cdots \times p$是奇数，记为奇数$2m+1$，其平方是$4m(m+1)+1$，这是一个形如$8k+1$的数，故而$q$是一个形如$8k+5$的数.根据论断，$q$的任何素因数均形如$4k+1$，也即均形如$8k+1$或者$8k+5$，而形如$8k+1$的两个数的乘积仍然是一个形如$8k+1$的数，所以$q$的素因数中至少有一个$8k+5$型的素数.而这个素数又不能在$2,3,\cdots ,p$当中，所以原假设不成立.即存在无穷多个形如$8k+5$的素数.因为形如$8k+5=4(2k+1)+1$的素数都是$4k+1$型的，故存在无穷多个形如$4k+1$的素数.

$3$.如果自然数$n$恰可被$r$个不同的素数$p_1 ,\cdots ,p_r $整除，则小于$n$且与$n$互素的整数的个数

$$\varphi (n)=n(1-\dfrac{1}{p_1 } )\cdots (1-\dfrac{1}{p_r } ).$$

函数$\varphi :\mathbb{N} \to \mathbb{N} $叫作欧拉函数.

证明公式当$n\leq 25$时，以及当$n=p^m$时成立.

证明：$(1)\;$当$n=p^m$时，不大于$p^m$之$p^m$个正整数中，有$p,2p,\cdots ,p^{m-1}p$共$p^{m-1}$个为$p$之倍数，其他皆与$p$互素.故

$$\varphi (p^m) =p^m -p^{m-1} =p^m (1-\dfrac{1}{p} ).$$

$(2)\;a$.引理.设$a,b,c\in \mathbb{N} $，则$(a,bc)=1\Leftrightarrow (a,b)=1$且$(a,c)=1$.

证明：若$(a,bc)=1$，记$(a,b)=d$，则$d\mid a$且$d\mid b$，从而$d\mid bc$，可知$1=(a,bc) \geq d$，故$d=1$，即$(a,b)=1$.

同理可证$(a,c)=1$.

若$(a,b)=1$且$(a,c)=1$，记$(a,bc)=d’ > 1$，则存在素因数$p\mid d’$，由于$d’\mid a$且$d’\mid bc $，另外$p > 1$，故$p\mid bc $且$p\mid a(p > 1)$，那么$p\mid b$或$p\mid c(p > 1)$.

如果$p\mid b$，因为$p\mid a$，所以$(a,b)\geq p > 1$，这与$(a,b)=1$矛盾.故$p\nmid b$.

同理，如果$p\mid c $，则$(a,c)\geq p > 1$，这也与$(a,c) =1$矛盾，故$p\nmid c$.

结合上面两个讨论，知原假设$d’ > 1$不成立，即$d’=1$，$(a,bc)=1$.

$b\;$若$(m,n)=1$，则$\varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)$.

证明：首先注意到$\varphi (1)=1$，故$m,n$中有一个数为$1$时，$\varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)$显然成立.现假设$m > 1$且$n > 1$，并把从$1$到$mn$的自然数排成一个$n\times m$的方阵：

$$\begin{matrix}
1 & 2 & \cdots & r & \cdots & m \\
m+1 & m+2 & \cdots & m+r & \cdots & 2m \\
2m+1 & 2m+2 & \cdots & 2m+r & \cdots & 3m \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
(n-1)m+1 & (n-1)m+2 & \cdots & (n-1)m+r & \cdots & nm \\
\end{matrix} $$

那么$\varphi (m\cdots n)$为上面这组数中与$mn$互素的自然数的个数，由$a$引理知它等于这组数中同时与$m,n$都互素的自然数的个数.

注意到$(km+r,m)=(r,m)$，所以当$(r,m)=1$时，第$r$列中的每一个数都与$m$互素，从而这$m$列数中共有$\varphi (m)$列数与$m$互素.

下面再证明这$\varphi (m)$列的每列数中，恰好有$\varphi (m)$个自然数与$n$互素，这样就能证明共有$\varphi (m)\cdot \varphi (n)$个数，既与$m$互素，又与$n$互素，得出定理为真.

事实上，从第$r$列看，因为数$(r,m)=1$，故这列数中的$n$个数中，任意两个数被$n$除时，所得余数都不会相同.若不然，假设$im+r$的$jm+r$被$n$除同余，则$(im+r)-(jm+r)=kn$，其中$0\leq j \leq i\leq n$，$k\in \mathbb{N}$，于是有$(i-j)m=kn$.因为题设已有$(m,n)=1$，故$n\mid (i-j)$，但这是不可能的.

可见这第$r$列中的$n$个数被$n$除的余数分别是$0,1,2,\cdots ,(n-1)$（不计顺序），而这$n$个数中与$n$互素的自然数个数正是$\varphi (n)$，即第$r$列中存在$\varphi (n)$个与$n$互素的数.

这就证明了$\varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)$.

$(3)\;$当$n\leq 25$时，因为素因数的个数$r\in \mathbb{N} $，故可考虑采用数学归纳法（下设$n_k $表有$k$个素因数的自然数$n$）.

当$r=1$时，由$(1)$知$\varphi (n)=n(1-\dfrac{1}{p} )$成立；

设$r=k$时，$\varphi (n_k )=n_k (1-\dfrac{1}{p_1 } )\cdots (1-\dfrac{1}{p_k } ) $成立；注意到加入第$k+1$个素因数$p_{k+1} $后，有

$$(p_1^{a_1 } ,p_2^{a_2 } ,\cdots ,p_k^{a_k } ,p_{k+1}^{a_{k+1} } ) =1,$$

且利用$(2)\;b$的结论：当$(m,n)=1$时，有$\varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)$；于是由归纳假设就有

$$\begin{align}
\varphi (n_{k+1} ) & =\varphi [(p_1^{a_1 } \cdot p_2^{a_2 } \cdots p_k^{a_k } )\cdot p_{k+1}^{a_{k+1} } ] \\
& =\varphi (p_1^{a_1 } \cdot p_2^{a_2 } \cdots p_k^{a_k } )\cdot \varphi (p_{k+1}^{a_{k+1} } )\\
& =n_k (1-\dfrac{1}{p_1 } )\cdots (1-\dfrac{1}{p_k } ) \cdot p_{k+1}^{a_{k+1} } (1-\dfrac{1}{p_{k+1} } ) \\
& =n_k \cdot p_{k+1}^{a_{k+1} } (1-\dfrac{1}{p_1 } )\cdots (1-\dfrac{1}{p_{k+1} } ) \\
& =n_{k+1} (1-\dfrac{1}{p_1 } )\cdots (1-\dfrac{1}{p_{k+1} } ),
\end{align}$$

从而$r=k+1$时，定理成立.

综上，对任意$r\in \mathbb{N} $，都有

$$\varphi (n) =n(1-\dfrac{1}{p_1 } )\cdots (1-\dfrac{1}{p_r } ).$$

$4$.运用二项式定理，对$n$作归纳证明，若$p$是素数，则$n^p-n$对任意$n\in \mathbb{Z} $可以被$p$整除.

证明：当$n=0$及$n=1$时显然成立，因为$p\mid 0^p-0$且$p\mid 1^p-1$.假设当$a$为某正整数时$p\mid n^p -n$，我们考虑$(n+1)^p-(n+1)$是否可以被$p$整除.由二项式定理可知

$$(n+1)^p =n^p+{p \choose 1}a^{p-1} +\cdots +{p \choose p-1}a^1 +1$$

上式等号右边除了头尾之外的每一项都是$p$的倍数，因此，有

$$p\mid (n+1)^p-n^p-1.$$

又由于我们假设$p\mid n^p-n$，所以由上式可得

$$p\mid (n+1)^p-n-1,$$

因此$(n+1)^p-(n+1)$可以被$p$整除.数学归纳法的证明于此完成.

故若$p$是素数，则$n^p-n$对任意$n\in \mathbb{Z} $可以被$p$整除.