初等整除性性质

整除性是数论中的一个关键概念。我们说一个整数 $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\,$ 不是质数的乘积。