整数. 整数的整除性

我们知道在自然数系内方程$a+x=b$有解当而且仅当$a\leq b$.当$a\leq b$时，这方程的解$x$记作$b-a$，叫做$b$减$a$的差.这意味着在自然数系内当$b\geq a$时$b$减$a$有意义，$b-a$表示一个自然数，它是这方程的解，否则$b-a$不能表示自然数，因而无意义.为了使得自然数的差$b-a$恒有意义.需要将自然数系加以扩充.我们从经验得到启示，一个扩充的办法是引进“正”和“负”的概念.当自然数$b>a$时，$b-a$表示正整数，若$b<a$时，$b-a$表示负整数.为了从数学上统一处理，我们的作法如下：

作自然数系的笛卡尔积${\bf N}\times {\bf N}=\lbrace (a,b)\mid a,b\in {\bf N}\rbrace $.$(a,b)$意味着自然数$a,b$的差$a-b$.由于有不同的$(a,b)$表示同一个差，就需要在${\bf N}\times {\bf N}$中引进一个等价关系$\sim$：

$$(a,b)\sim (c,d)\Leftrightarrow a+d=b+c.$$

容易验证这是一个等价关系.包含$(a,b)$的等价类记作$\overline{(a,b)}$.商集${\bf N}\times {\bf N}/\sim$记作$\bf Z$.这就是我们的整数集合.在$\bf Z$内定义加法和乘法如下：

$$\overline{(a,b)}\oplus \overline{(c,d)}=\overline{(a+c,b+d)},$$

$$\overline{(a,b)}\odot \overline{(c,d)}=\overline{(ac+bd,ad+bc)}.$$

不难验证，上述定义与类的代表的取法无关.由于自然数的运算满足交换律、结合律和分配律，那么整数集$\bf Z$的运算也满足同样的运算规律，这是容易验证的.此时$\bf Z$称为整数环.显然$\overline{(0,0)}$是$\bf Z$的零元素，$\overline{(1,0)}$是单位元素.用$\overline{(a,b)}$表示整数，符号未免累赘，需要简化.当$a\geq b$时，方程$a=b+x$在自然$\bf N$中有唯一解$x=n$.于是$\overline{(a,b)}$可以写成$\overline{(n,0)}$.当$a 0 $时，$\overline{(n,0)}$和$\overline{(0,n)}$分别叫做正、负整数.自然数系$\bf N$到整数环$\bf Z$有一个自然映射$n\mapsto \overline{(n,0)}$，它是单射而且保持加法和乘法，就是说，若$n\mapsto \overline{(n,0)}$，$m\mapsto \overline{(m,0)}$，则因$\overline{(n+m,0)}=\overline{(n,0)}\oplus \overline{(m,0)}$，$\overline{(n\cdot m,0)}=\overline{(n,0)}\odot \overline{(m,0)}$而有$n+m\mapsto \overline{(n,0)}\oplus \overline{(m,0)}$，$n\cdot m\mapsto \overline{(n,0)} \odot \overline{(m,0)}$.因此我们可以将自然数$n$与正整数$\overline{(n,0)}$和零$\overline{(0,0)}$等同，使得自然数系$\bf N$成为整数环$\bf Z$的一部分，而且$\bf N$的加法和乘法在$\bf Z$内仍然保持不变.因此整数运算符号$\oplus$和$\odot$也可以简记成$+$和$\cdot$，负整数$\overline{(0,n)}$可简单记成$-n$.于是非负整数的运算和自然数的运算相同.负整数与负整数之间、负整数与非负整数之间的运算表示如下：

$$(-n)+(-m)=-(n+m),$$

$$n+(-m)=(-m)+n=\begin{cases} n-m,n\geq m， \\ -(m-n)n<m，\end{cases}$$

$$(-n)\cdot (-m)=n\cdot m,$$

$$n\cdot (-m)=(-m)\cdot n=-n\cdot m.$$

以后用$a,b,c,\cdots$表示任意整数.现在$\bf Z$内引进负元素的概念.对每个整数$a$，存在一个唯一的整数$b$使得$a+b=0$.因为若$a=n\in \bf N$，则$b=-n$；若$a=-n,n\in \bf N$，则$b=n$.$b$叫做整数$a$的负元素，记成$b=-a$，同时$a$也是整数$-a$的负元素，因而有

$$-(-a)=a.$$

由上可知$-a$是$a$的负元素，但$-a$不必是负整数.负元素和负整数是两个不同的概念.进而在$\bf Z$内引进减法.对任意两个整数$a,b$，规定

$$a-b=a+(-b).$$

最后，一般方程$a+x=b$方程$\bf Z$内恒有解而且只有一解$x=b-a$.由此可知整数环有加法消去律；若$a+c=b+c$，则$a=b$.两个非零整数的积不能等于零，从而推出整数环还有乘法消去律：若$ac=bc$且$c\neq 0$，则$a=b$.

下面引进整数环的序，即整数的大小.对于任意整数$a,b$，规定

$$a\leq b \Leftrightarrow b-a\in \bf N.$$

若$a\leq b$且$a\neq b$，则记成$aa$).整数的序有如下的性质：

$i)ab$必有一而且只有一成立；

$ii)$若$a\leq b$且$b\leq c$，则$a\leq c$；

$iii)$若$a\leq b$，则$a+c\leq b+c$，对任意$c\in \bf Z$；

$iv)$若$a\leq b$且$c>0$，则$ac\leq bc$.

自然数的序在整数环内仍然保持不变.

整数$a$的绝对值$\mid a\mid $规定如下

$$\mid a\mid =\begin{cases} a； & 若a\geq 0， \\ -a， & 否则，\end{cases}$$

绝对值的性质有

$$\mid a\mid =0\Leftrightarrow a=0，$$

$$\mid a+b\mid \leq \mid a\mid +\mid b\mid ,$$

$$\mid ab\mid =\mid a\mid \cdot \mid b\mid .$$

下面来看整数的整除性.在整数环$\bf Z$内已经知道方程$a+x=b$恒有解，但是方程$ax=b(a\neq 0)$则不必有解.为了使得方程$ax=b(a\neq 0)$恒有解，解决的方法就是仿照从自然数系构造整数环的方法将整数环扩充有理数域.这是初等代数中早已解决了的问题.这种构造方法将在第三章中推广到整环上去.在引论中我们限制在整数环$\bf Z$中研究方程$ax=b$有解的条件，这样将导出整数环的整除性和同余式的理论.在中、小学已经知道判断上述方程是否有解的一个可行的方法带余除尘.从带余除法得到的结论就是

除法算式对任一对整数$a,b$，$b\neq 0$，存在一对整数$q$和$r$满足

$$a=b\cdot q+r,0\leq r<\mid b\mid .$$

而且这样的$q$和$r$是唯一的.$r$称为$a$被$b$除的余数.

证明 当$a\geq 0$，$b>0$时，用$b$对$a$作带余除法，可得到一个商数$q$和适合条件的余数$r$.我们在这里不打算给出正式的证明.$a,b$的其余情况不难归结为上述情况.下面证明$q,r$的唯一性.设有两对$q_{i},r_{i},i=1,2$使得

$$a=q_1b+r_1 ,0\leq r_1 <\mid b\mid ,$$

$$a=q_2b+r_2 ,0\leq r_2 <\mid b\mid .$$

两式相减得

$$(q_2-q_1)b=r_1-r_2.$$

取绝对值

$$\mid q_2-q_1\mid \mid b\mid =\mid r_1-r_2\mid .$$

假若$r_1\neq r_2$，则$0<\mid r_1-r_2\mid <\mid b\mid $，从而$\mid q_2-q_1\mid \neq 0$，$\mid q_2-q_1\mid \cdot \mid b\mid \geq \mid b\mid $，矛盾.所以$r_1=r_2$，从而$q_1=q_2$.$\blacksquare$

除法算式是整数的整除性理论的基础.

在除法算式中若$r=0$，则称$b$整除$a$，记作$b\mid a$.

对于整数$a,b$，若存在一个整数$c$使得$a=bc$，则称$b$是$a$的因子.$a$是$b$的倍数.从除法算式得到如下的

推论 一个非零整数$b$是整数$a$的因子，其充分必要条件是$b$整除$a$.

$1$和$-1$是任何整数的因子.每个整数是零的因子.每个整数和它的负元素都是它自身的因子，即$\pm a\mid a$.关于整除有下列基本性质：

1)若$a\mid b$且$b\mid a$，则$a=b$或$a=-b$.此时$a,b$叫做相伴.

2)若$a\mid b$且$b\mid c$，则$a\mid c$.

3)若$c\mid a$且$c\mid b$，则$c\mid ua\mid vb$，$u,v\in \bf Z$.

若整数$c\mid a$且$c\mid b$，则$c$叫做整数$a,b$的公因子.设$d$是整数$a,b$的一个公因子，若$a,b$的每个公因子也是$d$的因子，则$d$叫做$a,b$的一个最大公因子.

下面我们将证明任一对整数$a,b$都有最大公因子.在证明存在之前，先看一下$a,b$有多少最大公因子？设$d_1,d_2$为整数$a,b$的两个最大公因子.根据最大公因子的定义，由于$d_1$是$a,b$的最大公因子，有$d_2\mid d_1$.又因$d_2$也是$a,b$的最大公因子，有$d_1\mid d_2$，所以$d_1,d_2$相伴.因此任一对整数最多有一对相伴的最大公因子.

定理2 任一对不全为零的整数$a,b$都有最大公因子，而且它可以表成$a,b$的一个组合$ua+vb$，$u,v\in \bf Z$.

证明 考察$a,b$的一切组合的绝对值集合$S=\lbrace \mid xa+yb\mid \mid x,y\in \bf Z\rbrace $.$S$是自然数系的一个非空子集，而且$S$还包含有不为$0$的自然数.根据$\bf N$的良序性质，$S$必然包含一个非零的最小自然数，记作$d$.于是$d$显然可表成$a,b$的组合$d=ua+vb$.首先证明$d\mid a$且$d\mid b$.假若$d\nmid a$.用$d$对$a$作带余除法$a=qd+r$，$0\leq r < d $.因$d\nmid a$，$r>0$.于是

$$r=a-qd=a-(ua+vb)=(1-qu)a-qvb.$$

将有$r\in S$.但是$0<r<d$，这与$d$的选取矛盾.所以$d\mid a$.同理$d\mid b$.其次，证明$d$是$a,b$的最大公因子.设$c$为$a,b$的任一公因子，则$c\mid a$且$c\mid b$，从而$c\mid d=ua+vb$.所以$d$是$a,b$的一个最大公因子.$\blacksquare$

综上所述可知任一对不全为零的整数$a,b$恰有一对相伴的最大公因子，以后提到$a,b$的最大公因子时总是指大于$0$的那一个，并记作$(a,b)$.计算$(a,b)$的一个有效的方法就是辗转相除法，这是大家所熟悉的，在这里不重复了.

如果两个不全为$0$的整数$a,b$的最大公因子为$1$，则$a,b$叫做互素.

定理3 互素有如下性质：

$i)$整数$a,b$互素的充要条件是$1$可以表成$a,b$的组合；

$ii)$若$c\mid ab$且$(c,a)=1$，则$c\mid b$；

$iii)$若$a\mid c$且$b\mid c$且$(a,b)=1$，则$a\cdot b\mid c$；

$iv)$若$(a,c)=1$，$(b,c)=1$，则$(a\cdot b,c)=1$.

证明

$i)$显然.

$ii)$ 因为$(c,a)=1$，存在$u,v\in \bf Z$，使得$uc+va=1$.两端乘以$b$，$ucb+vab=b$.由于$c\mid cb$且$c\mid ab$，有$c\mid b$.

$iii)$ 因为$a\mid c$，$c$可写成$ac_1$.由于$b\mid ac_1$且$(b,a)=1$，根据$ii)$，有$b\mid c_1$.于是$c_1$可写成$c_1=bc_2$.最后$c=abc_2$，从而$ab\mid c$.

$iv)$因为$(a,c)=1$，存在$u,v\in \bf Z$使得$ua+vc=1$.因为$(b,c)=1$，存在$r,s\in \bf Z$使得$rb+sc=1$.于是

$$1=(ua+vc)(rb+sc)=urab+(usa+vrb+vsc)c,$$

根据$i)$，$(a\cdot b,c)=1$.$\blacksquare$

如果一个大于$1$的整数$p$除了$\pm 1$和$\pm p$外没有其它因子，则$p$叫做一个素数.

推论 设$p$为一素数，则

$i)$对任一整数$a$，若$p\nmid a$，则$(p,a)=1$；

$ii)$若$p\mid ab$，则$p\mid a$或$p\mid b$.

证明

$i)$设$d=(p,a)$.因为$p$为一素数，$d$只能是$p$或者$1$.若为前者，则有$p\mid a$，与假设矛盾，所以$d$只能是$1$，即$(p,a)=1$.

$ii)$设$p\mid ab$.若$p\nmid a$，由于$i)$有$(p,a)=1$.根据定理3，$ii)$得$p\mid b$.$\blacksquare$

最后证明

算术基本定理 每个大于$1$的整数$a$可以写成有限多个素数的乘积$a=p_1p_2\cdots p_r$，而且这些素因子按大小顺序排列后，写法只有一种.

证明 首先证明$a$可以分解成有限多个素数的乘积，对$a$作归纳法.假设对所有整数$a$，$1<a<n$，$a$可以写成有限多个素数的乘积，从而证明当$a=n$时$a$也可以写成有限多个素数的乘积.若$a$为素数，则$a$本身就是一种写法，设$a$不是素数，则$a$有一个因子$a_1$，使得$1<a_1<a$，于是$a$可分解成$a=a_1a_2$，从而也有$1<a_2<a$.根据归纳法，$a_1$和$a_2$分别可以分解成有限多个素因子的积.因而$a$也可以分解成有限多个素因子的积.其次证分解的唯一性.设$a$有两种分解

$$a=p_1p_2\cdots p_r=q_1q_2\cdots q_s,$$

其中$p_i$和$q_i$都是素数.求证$r=s$且$q_i$在适当调换脚标后有$q_i=p_i$，$i=1,\cdots ,r$.对$r$作归纳法.当$r=1$，$a=p_1$为素数，因而$s=1$，$p_1=q_1$.假设对$r-1$分解是唯一的，从而证明对$r$也是唯一的.根据素数的性质，从$p_1\mid a=q_1q_2\cdots q_s$，可知$p_1$整除某个$q$.设$p_1\mid q_1$.于是$q_1=p_1b$.由于$q_1$也是素数，推出$b=1$，$q_1=p_1$.从上式两端消去$p_1$得$p_2\cdots p_r=q_2\cdots q_s$.根据归纳法假设有$r-1=s-1$而且适当改换$q_i$的脚标后有$q_i=p_i$，$i=2,\cdots ,r$.这就证明了$a$的分解是唯一的.$\blacksquare$

在基本定理$a$的分解式中将相同的素因子归写成幂的形式，于是就得到$a$的标准分解式

$$a=p_1^{e_1}p_2^{e_2}\cdots p_i^{e_i},e_i\geq 1,p_i\neq p_j,i\neq j.$$

整除的条件也可以利用标准分解式来说明.任给两个大于$1$的整数$a,b$，设$p_{1},\cdots ,p_{r}$是$a$和$b$的全部不同的素因子.于是$a,b$有分解式

$$a=p_1^{s_1}p_2^{s_2}\cdots p_r^{s_r},s_i\geq 0,$$

$$b=p_1^{t_1}p_2^{t_2}\cdots p_r^{t_r},t_i\geq 0,$$

容易证明$a\mid b$的充要条件是$s_i\leq t_i$，$i=1,\cdots ,r$.