整除性

定义 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$ 是正的。

$T$ 中有最小元 $r=a-bq$($q$ 和 $r$ 的值如定理中所述)。

根据 $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$。(换而言之，$\frac{a}{d}$ 与 $\frac{b}{d}$ 互质)。

证明： 已知 $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}$ 的时候，从后往前依次构造出相应的解。

在用欧几里得算法求 $(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$ 的一个特解。

$a=99,b=78,a\%b=21$，因此 $78\times x_0+21\times y_0=3$，可以写成：$b\times x_0+(a\%b)\times y_0=3$，即 $bx_0+(a- \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$ 的一个特解。

代码：

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$的线性组合中的最小正整数。