初等数论/整数的基本性质

数论是奠基于算术之上的，所以在学习数论之前，要先知道以下关于整数的性质：

整数集合

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