初等整除性性質

整除性是數論中的一個關鍵概念。我們說一個整數 $a$ 能被非零整數 $b$ 整除，當且僅當存在一個整數 $c$ 使得 $a=bc$ .

例如，整數 123456 能被 643 整除，因為存在一個非零整數 192，使得 $123456=643\cdot 192\,$ .

我們用豎線來表示整除性: $a|b$ 表示 "a 整除 b"。例如，我們可以寫 $643|123456\,$ .

如果 $b$ 不能被 $a$ 整除，我們寫 $a\nmid b$ 。例如， $5\nmid 12$ .

以下定理說明了整除性的若干重要性質。

定理 1

假設 $a,b,d,r,\,$ 和 $s\,$ 是整數，並且 $d|a$ 和 $d|b\,$ 。那麼 $d|(ra+sb)\,$ .

證明

設 $a,b,d,r,\,$ 和 $s\,$ 為整數，並假設 $d|a$ 和 $d|b\,$ 。則存在整數 $e\,$ 和 $f\,$ 使得 $a=de\,$ 和 $b=df\,$ 。因此

$ra+sb=rde+sdf=d(re+sf).\,$

我們知道 $re+sf\,$ 也是一個整數，因此 $d|(ra+sb)\,$ 。

推論

假設 $a,b,d\,$ 和 $r\,$ 為整數，且 $d|a$ 和 $d|b\,$ 。則 $d|(a+b),d|(a-b),\,$ 以及 $d|ra\,$ 。

證明：令 $r=1$ 且 $s=1$ 代入定理 1 可得 $d|(a+b)\,$ 。類似地，令 $r=1$ 且 $s=-1$ 可得 $d|(a-b)\,$ 。最後，令 s=0 可得 $d|ra\,$ 。

定理 2

如果 $a,b,c\,$ 是整數，且 $a|b\,$ 以及 $b|c\,$ ，則 $a|c\,$ 。

證明

令 $a,b,$ 和 $c$ 是整數，並假設 $a|b\,$ 以及 $b|c\,$ 。則 $b=ad\,$ 且 $c=be\,$ ，對於一些整數 $d\,$ 和 $e\,$ 。

然後 $c=ade=a\left(de\right)\,$ ，因此 $a|c\,$ 。

定理 3

設 $a,b,c\,$ 為整數。則 $a|b\,$ 當且僅當 $ac|bc\,$

證明

設 $a,b,c\,$ 為整數。假設 $a|b\,$ .

則存在整數 $d$ 使得

$b=ad$ .

因此，可以得出

$bc=\left(ac\right)d$ ，因此 $ac|bc\,$ .

反過來，我們假設 $ac|bc\,$ .

則存在整數 $d\,$ 使得

$bc=\left(ac\right)d$ ，因此 $c(b-ad)=0.$

我們知道 c 不為零，因此

$b-ad=0,\,$ 即 $b=ad$ 。因此， $a|b$ .

質數和合數

大於一的自然數 *p* 如果只有兩個不同的自然數因子，即自身和 1，則稱為**質數**。前十一個這樣的數字是 2、3、5、7、11、13、17、19、23、29 和 31。然而，正如下面將證明的那樣，質數是無限的。

大於一且不是質數的自然數稱為**合數**。因此，4、6、8、9、10、12、14、15 和 16 是前幾個合數。

請注意，數字 1 是唯一既不是質數也不是合數的自然數。

定理 4

算術基本定理 (FTA)

每個合數正整數 *n* 都是質數的乘積。此外，這些乘積在因子順序上是唯一的。

證明

我們用反證法來證明這個定理。

假設存在一個正合數，它不是質數的乘積；設 *N* 是最小的這樣的整數。由於 *N* 是合數，它可以寫成 *N* = *a* *b*，其中 *a* 和 *b* 是整數，且 *a*，*b* > 1。

由於N不是素數的乘積，因此a和b中至少有一個不是素數的乘積；不失一般性，假設a不是素數的乘積。

然後，由於a>1，a是合數，因此a是一個不是素數乘積的正合數。

但是，由於a<N，這與我們假設N是最小的此類數相矛盾。

因此，不存在最小的此類數，因此不存在不是素數乘積的合數正整數。

唯一性的證明留給讀者。

另一種證明

這是一個歸納證明。

當 $k=2$ 時，語句“k是合數意味著k是素數的乘積”為真。

設 $N$ 為一個整數 $\geq 2$ .

假設該語句對所有 $k\leq N$ 都成立。

$N+1$ 要麼是合數，要麼是素數。如果 $N+1$ 是素數，則該語句對 $k=N+1$ 成立。

如果 $N+1$ 是合數，則 $N+1$ 可以被某個素數 $p<N+1$ 整除，因此 $k=N+1$ 可以寫成k=pa，其中p是素數，a是一個整數，且 $1<a<N+1$ 。然後a要麼是素數，要麼是合數；如果它是合數，則根據我們的歸納假設，它是一個素數的乘積。

因此 $N+1$ 可以寫成素數的乘積。

因此，該語句對所有 $k\leq N+1$ 成立，因此根據歸納法，對所有 $\mathbb {N}$ 成立。

唯一性的證明留給讀者。

定理 5

素數有無窮多個。

證明

假設只有 $k\,$ 個素數。

設這些素數為： $p_{1},p_{2},...,p_{k}\,$ .

令 $n=p_{1}p_{2}...p_{k}+1.\,$ 那麼，要麼 $n$ 是質數，要麼它是質數的乘積。如果它是質數的乘積，它必須能被某個質數 $p_{i}$ 整除，其中 $i$ 是某個整數。然而， ${\frac {n}{p_{i}}}={\frac {p_{1}p_{2}...p_{k}+1}{p_{i}}}=p_{1}p_{2}...p_{i-1}p_{i+1}...p_{k}+{\frac {1}{p_{i}}}$ ，顯然不是整數： $n$ 不能被 $p_{i}$ 整除。因此， $n\,$ 不是質數的乘積。