初等數論/整數的基本性質

數論 > 初等數論 > 初等數論/整數的基本性質

---

數論是奠基於算術之上的，所以在學習數論之前，要先知道以下關於整數的性質：

整數集合

整數集合，即所有的整數，像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}$)

習題