初等数论入门
MinimumSpanningTree
·
·
算法·理论
整除性
定义 1
如果 a 和 b 为整数且 a\neq0，我们说 a 整除 b 是指存在整数 c 使得 b=ac。如果 a 整除 b，我们还称 a 是 b 的一个因子，且称 b 是 a 的倍数。
如果 a 整除 b，则将其记为 a|b，如果 a 不能整除 b，则记其为 a\nmid b。
定理 1
如果 a，b 和 c 是整数，且 a|b，b|c，则 a|c。
证明：
因为 a|b，b|c，故存在整数 e 和 f，使得 ae=b，bf=c。
因此 c=bf=(ae)f=a(ef)，从而得到 a|c。
例如： 因为 11|66，66|198，故由定理 1 可知 11|198。
定理 2
如果 a，b，m 和 n 为整数，且 c|a，c|b，则 c|(ma+nb)。
证明：
因为 c|a 且 c|b，故存在整数 e 和 f，使得 a=ce，b=cf。
因此，ma+nb=mce+ncf=c(me+nf)，从而 c|(ma+nb)。
例如： 由于 3|21，3|33，故由定理 2 可知 3 能够整除 5\times21-3\times33=105-99=6。
定理 3 带余除法
如果 a 和 b 是整数且 b>0，则存在唯一的整数 q 和 r，使得 a=bq+r,0\le r<b。
在带余除法给出的公式中，我们称 q 为商，r 为余数，我们还称 a 为被除数，b 为除数。
例如：如果 a=133，b=21，则 q=6，r=7，因为 133-21\times6+7 且 0<7<21。
类似地，如果 a=-50，6=8，则 q=-7，r=6，因为 -50=8\times(-7)+6 且 0<6<8。
我们注意到 a 能被 b 整除当且仅当在带余除法中的余数为 0。
（1）存在性
考虑形如 a-bk 所有整数集合 S，其中 k 为整数。设 T 是 S 中的所有非负整数构成的集合，T 是非空的，因为当 k 是满足 k<a\div b 的整数时，a-bk 是正的。
根据 $r$ 的构造可知 $r\geq0$，且容易证明 $r<b$。
如果 $r\geq b$，则 $r>r-b=a-bq-b=a-b(q+1)\geq 0$，这与我们选择 $r=a-bq$ 为形如 $a-bk$ 的整数中的最小元矛盾，因此 $0\le r<b$。
## 最大公因数
### 定义 2
不全为零的整数 $a$ 和 $b$ 的最大公因子是指能够同时整除 $a$ 和 $b$ 的最大整数。
$a$ 和 $b$ 的最大公因子记作 $(a,b)$，（有时也记作 $\gcd(a,b)$，特别是在非数论的著作中我们将一直沿用传统的记号 $(a,b)$，虽然有时候这种记法也表示有序数对）。注意当 $n$ 为正整数时，$(0,n)=(n,0)=n$，虽然所有的正整数都能整除 $0$，我们还是定义 $(0,0)=0$ 这样可以确保关于最大公因子的相关结论在所有情况下均成立。
**例如：** $24$ 和 $84$ 的公因子有 $\pm1$，$\pm2$，
\pm3，\pm4，\pm6，
\pm12，因此 (24,84)=12。类似地，通过查看公因子集合，我们有 (0,44)=44，(-6,-15)=3，(-17,289)=17$。
定义 3
设 a，b 均为非零整数，如果 a 和 b 最大公因子 (a,b)=1，则称 a 与 b 互质。
注意由于 -a 的因子与 a 的因子相同，故有 (a,b)=(|a|,|b|)，其中 |a| 表示 a 的绝对值，因此，我们只关注正整数对的最大公因子。
定理 4
**证明：** 已知 $a$，$b$ 是整数，且 $(a,b)=d$。我们将证明 $\frac{a}{d}$，$\frac{b}{d}$ 除了 $1$ 之外没有其他的公因子。假设还有正整数 $e$ 使得 $e|(\frac{a}{d})$ 且 $e|(\frac{b}{d})$，那么存在整数 $k$ 和 $l$ 使得 $\frac{a}{d}=ke$，$\frac{b}{d}=le$，于是 $a=dek$，$b=del$。因此 $de$ 是 $a$，$b$ 的公因子，因为 $d$ 是 $a$，$b$ 的最大公因子，故 $de\le d$，于是 $e=1$。因此 $(\frac{a}{d},\frac{b}{d})=1$。
### 推论 1
如果 $a$，$b$ 为整数，且 $b\neq0$，则 $\frac{a}{b}=\frac{p}{q}$，其中 $p$，$q$ 为整数，且 $(p,q)=1$，$q\neq0$。
**证明：** 假设 $a$，$b$ 为整数且 $b\neq0$，令 $p=\frac{a}{d}$，$q=\frac{b}{d}$，其中 $d=(a,b)$，则 $\frac{p}{q}=\frac{a}{d}\div\frac{b}{d}$，由定理 4 可知 $(p,q)=1$，得证。
### 定理 5
令 $a$，$b$，$c$ 是整数，那么 $(a+cb,b)=(a,b)$。
**证明：**
令 $e$ 是 $a$，$b$ 的公因子，由定理 2 可知 $e|(a+cb)$，所以 $e$ 是 $a+cb$ 和 $b$ 的公因子。
如果 $f$ 是 $a+cb$ 和 $b$ 的公因子，由定理 2 可知 $f$ 整除 $(a+cb)-cb=a$，所以 $f$ 是 $a$，$b$ 的公因子，因此 $(a+cb,b)=(a,b)$。
### 定义 4
如果 $a$，$b$ 是整数，那么它们的线性组合具有形式 $ma+nb$，其中 $m$，$n$ 都是整数。
### 定理 6
两个不全为零的整数 $a$，$b$ 的最大公因子是 $a$，$b$ 的线性组合中最小的正整数。
**证明：**
令 $d$ 是 $a$，$b$ 的线性组合中最小的正整数，$d=ma+nb$, 其中 $m$，$n$ 是整数，我们将证明 $d|a$，$d|b$。
由带余除法，得到 $a=dq+r$，$0\le r<d$。
由 $a=dq+r$ 和 $d=ma+nb$，得到 $r=a-dq=a-q(ma+nb)=(1-qm)a-qnb$。
这就证明了整数 $r$ 是 $a$，$b$ 的线性组合。因为 $0\le r<d$，而 $d$ 是 $a$，$b$ 的线性组合中最小的正整数，于是我们得到 $r=0$（如果 $r$ 不是等于 $0$，那意味着 $r$ 才是所有线性组合中最小的正整数，这与 $d$ 是所有线性组合中最小的正整数矛盾），因此 $d|a$，同理可得，$d|b$。
我们证明了 $a$，$b$ 的线性组合中最小的正整数 $d$ 是 $a$，$b$ 的公因子，剩下要证的是它是 $a$，$b$ 的最大公因子，为此只需证明 $a$，$b$ 所有的公因子都能整除 $d$。
由于$d=ma+nb$，因此如果 $c|a$ 且 $c|b$，那么由定理 2 有 $c|d$，因此 $d>c$，这就完成了证明。
### 定义 5
令 $a_1$，$a_2$，$\cdots$，$a_n$ 是不全为零的整数，这些整数的公因子中最大的整数就是最大公因子。
$a_1$，$a_2$，$\cdots$，$a_n$ 的最大公因子记为 $(a_1,a_2,\cdots,a_n)$。（注意 $a_i$ 在这里面出现的顺序并不影响结果）
### 引理 1
如果 $A_1$，$A2$，$\cdots$，$An$，是不全为零的整数，那么 $(A1,A2,\cdots,A_{n-1},A_n)=(A1,A2,…,An-2,(An-1,An))$。
**证明：**
$n$ 个整数 $A_1$，$A_2$，$A_3$，$A_{n-1}$ 和 $A_n$ 的任意公因子也是 $A_{n-1}$ 和 $A_n$ 的公因子，因此也是 $(A_{n-1},A_n)$ 的因子。
因此，这 $n$ 个整数的公因子和由前 $n-2$ 个整数与后两个整数的最大公因子组成的集合的公因子完全相同，它们的最大公因子也一定相同。
## 裴蜀定理
如果 $a$ 与 $b$ 均为整数，则存在整数 $x$ 和 $y$ 满足 $ax+by=(a,b)$。
定理 6 容易证明正确性。
### 扩展欧几里得算法（$\text{exgcd}$）
下面用扩展欧几里得算法求出满足 $ax+by=(a,b)$ 的一个特解。
例如：$a=99,b=78$，令 $d=(a,b)=(99,78)=3$，求 $99x+78y=3$ 的一个特解。
在调用 $\text{exgcd}$ 的时候，从后往前依次构造出相应的解。
a|b|d|x|y|备注
---|---|---|---|---|---
$99$|$78$|$3$|$-11$|$14$|
$78$|$21$|$3$|$3$|$-11$|$78x+21y=3$ 的一个特解 $x=3,y=-11
21$|$15$|$3$|$-2$|$3$|$21x+15y=3$ 的一个特解 $x=-2,y=3
15$|$6$|$3$|$1$|$-2$|$15x+6y=3$ 的一个特解 $x=1,y=-2
6$|$3$|$3$|$0$|$1$|$6x+3y=3$ 的一个特解是 $x=0,y=1
3$|$0$|$3$|$1$|$0$|$3x+0y=3$ 的一个特解是 $x=1,y=0
在用欧几里得算法求 (99,78) 的时候，要先求 (78,21)。
假如已经求出 78x+21y=3 的一个解 x_0=3,y_0=-11，即 78\times x_0+21\times y_0=3。
那么可以由 78\times x_0+21\times y_0=3，构造出 99x+78y=3 的一个特解。
\frac{a}{b}b)y_0=3$，即 $ay_0+b(x_0-\frac{a}{b}y_0)=3$，即 $99y_0+78(x_0-\frac{99}{78}y_0)=3$。
那么只需要令 $x=y_0=-11,y=x_0-(99\div78)\times y_0=14$，就可以得到 $99x+78y=3$ 的一个特解，即 $-11,14$ 是 $99x+78y=3$ 的一个特解。
也就是说，在用欧几里得算法求 $(78,21)$ 的时候，若能返回 ${x0,y0}$ 使得满足 $78\times x_0+21\times y_0=3$，那么就能构造出一个特解 ${x,y}$ 满足 $99x+78y=3$ 的一个特解。
**代码：**
```cpp
void exgcd(int a,int b,int &d,int &x,int &y)
{
if(b==0)
{
d=a;
x=1;
y=0;
return;
}
exgcd(b,a%b,d,x,y);
int tmp=x;
x=y;
y=tmp-(a/b)*y;
}
```
**注意：**
若 $a<0$ 且 $b>=0$ 那么在求 $ax+by=(a,b)$ 的时候，可以先求出 $|a|x+by=(|a|,b)$ 的一组解 ${x_0,y_0}$，然后 ${-x_0,y_0}$ 就是原方程的一个解。
若 $a>=0$ 且 $b<0$ 的同理。若 $a<0$ 且 $b<0$ 的也同理。
### 定理 7
如果 $a$，$b$ 是正整数，那么所有 $a$，$b$ 的线性组合构成的集合与所有 $(a,b)$ 的倍数构成的集合相同。
**证明：**
假设 $d=(a,b)$。
首先证明每个 $a$，$b$ 的线性组合是 $d$ 的倍数。首先注意到由最大公因子的定义，有 $d|a$ 且 $d|b$ ，每个 $a$，$b$ 的线性组合具有形式 $ma+nb$，其中 $m$，$n$ 是整数。
由定理 2 ，只要 $m$，$n$ 是整数，$d$ 就整除 $ma+nb$，因此，$ma+nb$ 是 $d$ 的倍数。
现在证明每一个 $d$ 的倍数也是 $(a,b)$ 的线性组合。
由定理 6，存在整数 $r$，$s$ 使得 $(a,b)=ra+sb$。而 $d$ 的倍数具有形式 $jd$，其中 $j$ 是整数。
在方程 $d=ra+sb$ 的两边同时乘以 $j$，我们得到 $jd=(jr)a+(js)b$。
因此，每个 $d$ 的倍数是 $(a,b)$ 的线性组合。
### 推论 2
整数 $a$ 与 $b$ 互质当且仅当存在整数 $m$ 和 $n$ 使得 $ma+nb=1$。
**证明：**
如果 $a$，$b$ 互质，那么 $(a,b)=1$，由定理 6 可知，$1$ 是 $a$ 和 $b$ 的线性组合的最小正整数，于是存在整数 $m$，$n$ 使得 $ma+nb=1$。
反之，如果有整数 $m$ 和 $n$ 使得 $ma+nb=1$，则由定理 6 可得 $(a,b)=1$，这是由于 $a$，$b$ 不同为 $0$ 且 $1$ 显然是 $a$，$b$的线性组合中的最小正整数。
## 费马小定理
如果 $p$ 是一个质数，且 $\gcd(a,p)=1$，那么 $a^{p-1}\equiv1\pmod p$。
### 引理 2
如果 $p$ 是一个质数，且 $\gcd(a,p)=1$，构造一个序列：$A=\{1,2,3,\dots,p-1\}$，那么满足每一个 $A_i\times a\pmod p$ 都是独一无二的。
**证明：**
如果我们能证出对于任意的 $1\le i<j\le p-1$，都满足 $A_i\times a\pmod p\neq A_j\times a\pmod p$，那么这条引理就是成立的。
设 $A_i\times a\% p=k$，那么如果想要 $A_i\times a\pmod p= A_j\times a\pmod p$，就得让 $A_j\times a\% p=k$。要使余数不变，加上的数就必须是除数的倍数。但 $a\times(A_j-A_i)$ 不可能是 $p$ 的倍数，所以 $A_i\times a\pmod p\neq A_j\times a\pmod p$ 是恒成立的，证毕。
### 费马小定理的证明
构造一个序列 $A=\{1,2,3,\dots,p-1\}$。
$\because (A_i,p)=1,(A_i\times a,p)=1
又因为由引理 2 得出每一个 A_i\times a \pmod p 都是独一无二的，且 A_i\times a \pmod p < p，所以相当于每一个 A_i\times a 都对应了一个 A_i，就可以得出序列 A 有以下性质：
\prod_{i=1}^{p-1}A_i\equiv\prod_{i=1}^{p-1}(A_i\times a)\pmod p
设 f=(p-1)!, 则 f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p
\therefore a^{p-1}\times f \equiv f \pmod p
\therefore a^{p-1} \equiv 1 \pmod p
证毕。