初等数论入门

整除性

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