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

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

整數集合

整數集合，即所有的整數，像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}$ 相等。於是我們有：