初等数论/整数的基本性质

数论 > 初等数论 > 初等数论/整数的基本性质

---

数论是奠基于算术之上的，所以在学习数论之前，要先知道以下关于整数的性质：

整数集合

整数集合，即所有的整数，像0,1,-1,2,-2,......这一些整数形成的集合，就叫整数集合，或以$\mathbb {Z}$表示，自然数$\mathbb {N}$为其子集，但奇怪的是，整数集合和正整数集合内部的元素数量竟相等

整数集合的性质符合环的性质，意即其加减乘法皆自封(若对一种定义在X上的运算Y，当a和b皆为X的元素时，aYb亦为X的元素，则称运算Y自封)，以下将说明整数集合的性质

数学归纳法

若有一个命题$P(n)$，若能证明$P(n)$对$n=1$或其他给定的起始正整数$k$成立，且在假设对一个正整数$n=m>1$（或前面给定的正整数$k$），命题$P(n)$成立时，亦能证明$n=m+1$时命题$P(n)$成立，则命题$P(n)$对所有$n\in N$或$n\in N-\left\{1,2,3,...,k-1\right\}$皆成立，除了本法以外，尚有第二种数学归纳法，第二种数学归纳法将在稍后说明

加法篇

加法使用符号+，$a$加$b$，或称$a$和$b$相加可记为$a+b$

整数集合的加法（和减法）是封闭的（若$S$里面的元素透过一个定义在$S$上的运算，所得的结果的元素依然存在于$S$，且对所有$S$的元素都是如此，那么这个二元运算就是在$S$上封闭的），以下为加法（和减法）的性质：

• 加法有结合律，即对于任意整数$a$,$b$,$c$有$\left(a+b\right)+c=a+\left(b+c\right)$

• 加法有交换律，即对于任意整数$a$,$b$有$a+b=b+a$

• 加法有相消律，即对于任意整数$a$,$b$,$c$，若$a+c=b+c$，则可推出$a=b$

• 减法，若对整数$a$,$b$,c有$a=b+c$，则亦可记做$a-b=c$，但是减法无交换律

• 在整数中有一个元素0，使得对任意整数$a$有$a+0=a$且$a-0=a$

乘法篇

乘法使用符号‧，$a$乘$b$，或称$a$和$b$相乘可记为$a\cdot b$，但是若$a$或$b$至少有一个为未知数$x$，则乘号‧可省略（但若$a$和$b$皆为已知数，且皆以数字（非英文字母）表示，则乘号“‧”不可省略）

整数集合的乘法也是封闭的，以下为它的性质：

• 乘法有结合律，即对于任意整数$a$,$b$,$c$有$a\left(bc\right)=\left(ab\right)c$

• 乘法有交换律，即对于任意整数$a$,$b$有$ab=ba$

• 乘法有相消律，即对于任意整数$a$,$b$,$c$，若$ab=ac$，则可推出$b=c$ (a不能为零)

• 在整数中有一元素1，使得对任意整数$a$有$a\times 1=1\times a=a$

• 任意整数$a$和0相乘为0

大小关系

整数集合是一个有序集合，以下为整数中的序的关系(即一般所说的大小关系)

• 若$a>b$，则必有正整数$c$，使$b+c=a$

• 若$a<b$，且$b<c$，则$a<c$

• 若$a<b$，且$a$,$b$为正整数，则必有正整数$n$，使得$na>b$

• 若$a>b$且$c>d$，则$a+c>b+d$

• 对于任意整数$a$，有$a=a$

• 对于两个整数$a,b\in \mathbb {Z}$，$a<b$、$a>b$和$a=b$有且仅有一个成立

最大自然数原理与最小自然数原理

• 最小自然数原理：对于任意自然数的非空子集$X$，存在一元素$n$，使得任意的$x\in X$，都有$n\leq x$

事实上，对于任意有下界的非空集合$S$，若$S$为整数集合Z的一个子集，则在$S$中必存在一最小的数n，使得任意的$x\in Z$，都有$n\leq x$

• 最大自然数原理：对于任意有上界的非空子集$Y$，存在一元素$m$，使得任意的$y\in Y$，都有$m\geq y$

除法篇

除法使用符号$\div$，若$a$除以$b$，或$b$除$a$，记做$a\div b$

• 若$a$可被$b$整除，则记做$b|a$，或$a=bk$

• 若不能整除，即会剩余某数$c<a$，则记做$a=bm+c$

• 若$b$不能整除$a$，但是能找得到一数，使$b|a-c$，则此$a$,$b$,$c$可记做$a\equiv c$(${\bmod {b}}$)，后者亦可称$a$除以$b$同余于$c$

其他的一些名词的定义

• 因数：若$b|a$成立，则$b$是$a$的因数

• 倍数：若$b|a$，则$a$是$b$的倍数

• 质数：若一个大于1的正数$p$的正因数只有1,$p$，则称这个数$p$为质数

第二种数学归纳法

虽然比起前面所说的数学归纳法，第二种数学归纳法比较少用，但是第二种数学归纳法仍然为重要的证明方法，兹将之说明如下： 若对一个命题$P(n)$，在$n=1$(或指定的正整数$k$)时成立，在假设对所有符合$n<m$的正整数都成立时，能证明$P(n)$对$m$亦成立，则$P(n)$对所有正整数（或正整数集合$N-\left\{1,2,3,...,k-1\right\}$）都成立

第二种数学归纳法可以用最小自然数原理和反证法证明其为真

算术基本定理

任意大于1的正整数都能唯一地表示成由指定数量的特定质数的乘积

标准分解式

根据算术基本定理，任意正整数皆可表为唯一的若干个正质数的乘积，且因为这些质数没有次序上的问题，因此，可将相同的质数写成该质数的幂方也是没问题的，意即上面的a可改写为： a=$p_{1}^{q_{1}}p_{2}^{q_{2}}p_{3}^{q_{3}}......p_{n}^{q_{n}}$

算术基本定理的证明

先证明几个引理：

• 引理1：每个大于一的数都可以表示成质数的乘积，或本身为质数

引理1证明：用第二种数学归纳来证明，设正整数$n=2$时，2为质数，故成立，再假设当$2\leq n<m$时此引理成立，则当$n=m$时，若$m$为质数，则引理成立，若$m$不为质数时，$m$为合数，因此$m=pq$，其中$2\leq p,q<m$，因而由假设知$p$和$q$可表为质数的乘积，因而$m$亦可表为质数的乘积，因此引理亦对$n=m$成立，因此由数学归纳法得知，此引理对所有的正整数$n\geq 2$成立

• 引理2：若$p|ab$，且$p$是质数，则p|a或p|b至少有一个成立，另一方面，若$p$是质数，且若$p|a_{1}a_{2}a_{3}......a_{n}$成立，则$p|a_{1}$、$p|a_{2}$、$p|a_{3}$、......$p|a_{n}$至少有一成立

引理2证明：

• 由引理2引出的引理3：若$p,q_{1},q_{2},......,q_{k}$皆为质数，且$p|q_{1}q_{2}......q_{k}$则至少有一个$q_{j},1\leq j\leq k$使$p|q_{j}$

引理3证明：

算术基本定理证明：存在性由引理1可得知，现在来证唯一性：设有一数n，它的分解式为$n=p_{1}p_{2}p_{3}......p_{s}$，其中$p_{1},p_{2},p_{3},......,p_{s}$皆为质数，再设n存在另一个分解式$n=q_{1}q_{2}q_{3}......q_{r}$，设$r>s$，且$q_{1},q_{2},q_{3},......,q_{r}$亦皆为质数，而且$p_{1}\leq p_{2}\leq p_{3}\leq ......\leq p_{s}$及$q_{1}\leq q_{2}\leq q_{3}\leq ......\leq q_{s}$，则很明显地有$n=p_{1}p_{2}p_{3}......p_{s}=q_{1}q_{2}q_{3}......q_{r}$，由引理3知，必有一些$p_{i}$和$q_{j}$相等，且可推知这个关系是唯一的，因此现在将和$p_{1}$相等的数设为${q_{1}}'$，其他的也照做，意即$p_{1}={q_{1}}$、$p_{2}={q_{2}}'$、‧‧‧、$p_{s}={q_{s}}'$，而剩下来的则记为${q_{s+1}}',{q_{s+2}}',{q_{s+3}}',......,{q_{r}}'$，则由此及$n=p_{1}p_{2}p_{3}......p_{s}={q_{1}}'{q_{2}}'{q_{3}}'......{q_{r}}'$可推出$1={q_{s+1}}'{q_{s+2}}'{q_{s+3}}'......{q_{r}}'$意即此两个分解式之中所有的质数相等，与原假设矛盾，故n的分解式为唯一的

最大公因数与最小公倍数

最大公因数

假若对两个整数$a,b$，有一整数$n$，使$n|a$且$n|b$，则称$n$为$a$和$b$的公因数，若在$a$和$b$的公因数所形成的集合中，$n$是为其中最大的数字，则称这个$n$为$a$和$b$的最大公因数，或记做$(a,b)=n$，若$(a,b)=1$，则称$a$和$b$互质

最小公倍数

若有整数$m,a,b$，使得$a|m$且$b|m$，则称$m$为$a$和$b$的公倍数，若在$a$和$b$所有的正公倍数所形成的集合中，$m$是其中最小的数字，则称$m$为$a$和$b$的最小公倍数，或记做$[a,b]=m$，且若$(a,b)=1$，则$[a,b]=ab$

最大公因数和最小公倍数的性质

• 最大公因数：
  • $(a,b)=(|a|,b)=(a,|b|)=(|a|,|b|)$
  • 若$(a,b)=c$则$(a,b+ka)=c$，且在此$a,b,k$为任意整数，$c$为任意正整数
  • 若$(a,b)=c$则$(a,b,ka)=c$，且在此$a,b,k$为任意整数，$c$为任意正整数

辗转相除法

对于两个数$a$和$b_{1}$，有以下算法：

我们可以$d$表示$a,b$的公约数则$d|a$并且$d|b_{1}$
所以$a=k_{1}*d$并且$b_{1}=k_{2}*d$ $a-b=(k1-k2)*d$，
也就是说当$a<>b_{1}$时，$a$和$b_{1}$的最大公约数和$a-b_{1}$和$b_{1}$相等。于是我们有：

$a=q_{1}b_{1}+b_{2}$

$b_{1}=q_{2}b_{2}+b_{3}$

......

$b_{n}=q_{n+1}b_{n+1}$

其中($a$,$b_{1}$)=($b_{1}$,$b_{2}$)=......=($b_{n}$,$b_{n+1}$)

习题