文章目錄
  1. 1. 算术基本定理
  2. 2. $\mathbb{Z} $中的最大公约数和最小公倍数
  3. 3. $\mathbb{Z} $中的带余除法
  4. 4. 习题

本节的目的是简述整数的初等可除性质,以便在后面的章节中引用.进一步的结果将在第$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$整除.

文章目錄
  1. 1. 算术基本定理
  2. 2. $\mathbb{Z} $中的最大公约数和最小公倍数
  3. 3. $\mathbb{Z} $中的带余除法
  4. 4. 习题