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

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

---

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

整數集合

整數集合，即所有的整數，像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-\{1,2,3,...,k-1\}$皆成立，除了本法以外，尚有第二種數學歸納法，第二種數學歸納法將在稍後說明

加法篇

加法使用符號+，$a$加$b$，或稱$a$和$b$相加可記為$a+b$

整數集合的加法（和減法）是封閉的（若$S$裡面的元素透過一個定義在$S$上的運算，所得的結果的元素依然存在於$S$，且對所有$S$的元素都是如此，那麼這個二元運算就是在$S$上封閉的），以下為加法（和減法）的性質：

• 加法有結合律，即對於任意整數$a$,$b$,$c$有$(a+b)+c=a+(b+c)$

• 加法有交換律，即對於任意整數$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\le x$

事實上，對於任意有下界的非空集合$S$，若$S$為整數集合Z的一個子集，則在$S$中必存在一最小的數n，使得任意的$x\in Z$，都有$n\le x$

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

除法篇

除法使用符號$÷$，若$a$除以$b$，或$b$除$a$，記做$a÷b$

• 若$a$可被$b$整除，則記做$b|a$，或$a=bk$

• 若不能整除，即會剩餘某數$c<a$，則記做$a=bm+c$

• 若$b$不能整除$a$，但是能找得到一數，使$b|a-c$，則此$a$,$b$,$c$可記做$a\equiv c$($modb$)，後者亦可稱$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-\{1,2,3,...,k-1\}$）都成立

第二種數學歸納法可以用最小自然數原理和反證法證明其為真

算術基本定理

任意大於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\le n<m$時此引理成立，則當$n=m$時，若$m$為質數，則引理成立，若$m$不為質數時，$m$為合數，因此$m=pq$，其中$2\le p,q<m$，因而由假設知$p$和$q$可表為質數的乘積，因而$m$亦可表為質數的乘積，因此引理亦對$n=m$成立，因此由數學歸納法得知，此引理對所有的正整數$n\ge 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\le j\le 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\le p_2\le p_3\le ......\le p_s$及$q_1\le q_2\le q_3\le ......\le 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\text{'}$，其他的也照做，意即$p_1=q_1$、$p_2={q_2}^{\prime }$、‧‧‧、$p_s={q_s}^{\prime }$，而剩下來的則記為$q_{s+1}\text{'},q_{s^{\prime }+2},q_{s^{\prime }+3},......,{q_r}^{\prime }$，則由此及$n=p_1{p}_2{p}_3......p_s={q_1}^{\prime }{q_2}^{\prime }{q_3}^{\prime }......{q_r}^{\prime }$可推出$1=q_{s^{\prime }+1}{q}_{s^{\prime }+2}{q}_{s^{\prime }+3}......{q_r}^{\prime }$意即此兩個分解式之中所有的質數相等，與原假設矛盾，故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}$)