大公因与小公倍进阶
dingziyang888
·
·
算法·理论
前言
这是我和盟友两位五年级蒟蒻合作的数论合集第六篇文章，大佬们不喜勿喷，感谢您的收看。
辗转相除理论基础
带余除法的定义与证明
::::info[定义]{open}
对于任意的整数 a 与非零整数 b，存在唯一整数对 (q,r)，满足：
-
-
::::
接下来，我们来证明一下定义。
我们可以把 q 和 r 都表示出来，就已经证明出了存在性和第 1 条结论，下面给出结论 2 的伪证：
::::warning[伪证]{open}
证：令
q=[\frac{a}{b}],r=a-b[\frac{a}{b}]
则结论 1 已经满足。由取整的范围，
\frac{a}{b} - 1 < [\frac{a}{b}] \le \frac{a}{b}
两边同乘 b 得：
a-b < b[\frac{a}{b}] \le b
即
0 \le r < b。
::::
为什么说是伪证呢？因为如果 b<0，那么不等式两边同乘 b 时是要变号的，而上面的伪证并没有考虑到这一情况。而且结论 2 中 b 是带了绝对值的，如果按上面的伪证，就相当于绝对值没有任何作用，显然是不合理的。
::::success[正确的证明]{open}
证：
$$
q=[\frac{a}{b}],r=a-b[\frac{a}{b}]
$$
则结论 $1$ 已经满足。由取整的范围，
$$
\frac{a}{b} - 1 < [\frac{a}{b}] \le \frac{a}{b}
$$
两边同乘 $b$ 得：
$$
a-b < b[\frac{a}{b}] \le b
$$
即
$$
0 \le r < b=|b|。
$$
$2^\circ$ 若 $b < 0$，令
$$
q=\lceil\frac{a}{b}\rceil,r=a-b\lceil\frac{a}{b}\rceil
$$
则结论 $1$ 已经满足。由向上取整的范围，
$$
\frac{a}{b} \le \lceil\frac{a}{b}\rceil < \frac{a}{b}+1
$$
两边同乘 $b$ 得：
$$
a \ge b\lceil\frac{a}{b}\rceil > a+b
$$
即
$$
0 \le r < -b = |b|。
$$
综上，
1. $a=bq+r$；
2. $0 \le r < |b|$。
证毕。
::::
上面我们给出了结论 $2$ 的证明，接下来给出唯一性的证明。
---
可以设出两组 $q$ 和 $r$ 都满足条件，证两组相等即可。
::::success[证明]{open}
证：若 $(q_1,r_1),(q_2,r_2)$ 均满足条件，即
$$
a=bq_1+r_1=bq_2+r_2
$$
稍稍整理得：
$$
b(q_1-q_2)=r_2-r_1
$$
又由于
$$
0 \le r_1,r_2 \le |b|-1
$$
$$
\therefore |r_2-r_1| \le |b| -1 < |b|
$$
又
$$
b \mid r_2-r_1
$$
$$
\therefore r_2-r_1=0
$$
即
$$
r_1=r_2,q_1=q_2。
$$
故只存在一组，证毕。
::::
有了这个基础就可以正式进入大公因与小公倍的内容了：
### 大公因与小公倍的定义
三个基础的定义：
+ 设 $a_1,a_2$ 为两个不全为 $0$ 的整数。如果 $d \mid a_1$ 且 $d \mid a_2$，则称 $d$ 为 $a_1$ 和 $a_2$ 的**公因数**。一般地，设 $a_1,a_2,\dots,a_k$ 为 $k$ 个不全为 $0$ 的整数，如果 $d \mid a_1,d \mid a_2,\dots,d \mid a_k$，那么称 $d$ 为 $a_1,a_2,\dots,a_k$ 的**公因数**。
+ 我们考虑 $a_1,a_2,\dots,a_k$ 的所有公因数，显然其中一定有 $1$，即公因数一定存在，另外非 $0$ 整数的因数个数有限，从而 $a_1,a_2,\dots,a_k$ 的公因数个数有限，故必有最大值，这个最大值称为 $a_1,a_2,\dots,a_k$ 的**最大公因数**，记作 $(a_1,a_2,\dots,a_k)$。
+ 设 $a_1,a_2$ 为两个不全为 $0$ 的整数，如果 $a_1 \mid m$ 且 $a_2 \mid m$，那么称 $m$ 为 $a_1,a_2$ 的公倍数。一般地，设 $a_1,a_2,\dots,a_k$ 是 $k$ 个不全为 $0$ 的整数，如果 $a_1 \mid m,a_2 \mid m,\dots,a_k \mid m$，那么称 $m$ 为 $a_1,a_2,\dots,a_k$ 的**公倍数**。
+ 我们考虑 $k$ 个全不为 $0$ 的整数 $a_1,a_2,\dots,a_k$ 的所有公倍数，显然其中一定有 $|\prod_{i=1}^{k}a_i|$，即正的公倍数一定存在，从而 $a_1,a_2,\dots,a_k$ 的公倍数中一定存在最小值，叫做 $a_1,a_2,\dots,a_k$ 的**最小公倍数**，记作 $[a_1,a_2,\dots,a_k]$。
+ 若 $(a_1,a_2,\dots,a_k)=1$，则称 $a_1,a_2,\dots,a_k$ **互质**。
### 一个引理
::::info[引理]{open}
$$
\forall a,b,x \in \mathbb{Z},(a+bx,b)=(a,b)
$$
::::
可以设两个未知数分别表示等式两边，证明这两个数相等即可。简单计算可以发现，这两个数都是另一边的因数，那就好办了。
::::success[证明]{open}
证：设
$$
d=(a+bx,b),e=(a,b)
$$
则
$$
d \mid a+bx,d \mid b,e \mid a,e \mid b
$$
$$
d \mid a,e \mid a+bx
$$
故 $d$ 也是 $a$ 和 $b$ 的公因数，$e$ 是 $a+bx$ 和 $b$ 的公因数。则有
$$
d \le e,e \le d
$$
故
$$
d=e
$$
即
$$
(a+bx,b)=(a,b)。
$$
证毕。
::::
这一引理也为辗转相除奠定了坚实基础。
### 辗转相除求最大公因数
具体步骤：
对于任意两个非零整数 $a,b$，进行如下操作：
设
$$
a_1=a,b_1=b,a_1 \div b_1=q_1\dots r_1
$$
若 $r_1=0$，则
$$
(a,b)=(a_1,b_1)=b_1=b
$$
否则，对于任意的 $k \ge 2$，令
$$
a_k=b_{k-1},b_k=r_{k-1},a_k \div b_k=q_k\dots r_k
$$
若 $r_k=0$，则
$$
(a,b)=(a_1,b_1)=(b_1,r_1)=(a_2,b_2)=(b_2,r_2)=\dots=(a_k,b_k)=b_k
$$
若 $r_k \ne 0$，则重复操作。
由于 $r_k=b_{k+1}>r_{k+1}$，即 $\{r_k\}$ 单调递减且非负，因此最终一定会经过有限步使得 $r_m=0$，从而求出 $a,b$ 的最大公因数为 $b_m$。这一方法称之为**辗转相除法**，或称为**更相减损术**。
### 例题一
::::info[题目]{open}
求证：已知 $a$ 为正整数，则
$$
(a^3+2a,a^4+3a^2+1)=1。
$$
::::
简单辗转相除即可，这里的“除”考虑用大除法（长除法）实现。
::::success[完整解答]{open}
证：
$$
\begin{align*}
(a^3+2a,a^4+3a^2+1)&=(a^3+2a,a^2-a+1)\\
&=(2a,a^2-a+1)\\
&=(2a,1)\\
&=1。
\end{align*}
$$
证毕。
::::
### 例题二
::::info[题目]{open}
求证：
$$
\forall n \ge k \wedge n,k \in \mathbb{Z},(C_n^k,C_{n+1}^k,\dots,C_{n+k}^k)=1。
$$
::::
对于组合数的计算，有一个 ~~是人都知道的~~ 公式
$$
C_{n+1}^k=C_n^k+C_n^{k-1}。
$$
所以上标为 $k$ 的组合数都可以通过辗转相除弱化为 $k-1$，显而易见这里应当使用数学归纳法进行证明。
::::success[完整解答]{open}
证：$1^\circ$ $k=1$，
$$
LHS=(C_n^1,C_{n+1}^1)=1=RHS
$$
命题成立。
$2^\circ$ 若 $k=m$ 时命题成立，即
$$
(C_n^m,C_{n+1}^m,\dots,C_{n+m}^m)=1
$$
则 $k=m+1$ 时
$$
\begin{align*}
(C_n^{m+1},C_{n+1}^{m+1},\dots,C_{n+m+1}^{m+1})&=(C_n^{m+1},C_{n+1}^{m+1},\dots,C_{n+m}^{m+1},C_{n+m}^m)\\
&=(C_n^{m+1},C_{n+1}^{m+1},\dots,C_{n+m-1}^{m+1},C_{n+m-1}^m,C_{n+m}^m)\\
&=\dots\\
&=(C_n^m,C_{n+1}^m,\dots,C_{n+m}^m)\\
&=1。
\end{align*}
$$
由数学归纳法，命题成立。证毕。
::::
### 习题
::::info[习题一]{open}
$\forall n \ge 50$ 且 $n \in \mathbb{Z}$，求使得 $(4n+5,7n+5)>1$ 的所有 $n$ 之和。
::::
::::info[习题二]{open}
设 $n \ge 1$，求
$$
(n!+1,(n+1)!+1)
$$
的值。
::::
::::info[习题三]{open}
求证：
$$
\forall a,b \in \mathbb{Z},(2^{2^a}+1,2^{2^b}+1)=1。
$$
::::
## 裴蜀定理
::::info[定理内容]{open}
对于任意两个非 $0$ 整数 $a,b$，存在整数 $x,y$，使得 $ax+by=(a,b)$。
::::
先举个例子来感受一下这个定理讲的是什么。
---
比如说 $a=1234,b=567$，则 $(a,b)=1$，由于
$$
1234\div567=2\dots100
$$
则 $100$ 可以用 $1234$ 和 $567$ 表示出来，即
$$
100=1234-567 \times 2。
$$
再有
$$
567 \div 100=5\dots67
$$
那么 $67$ 就可以用 $100$ 和 $567$ 表示出来，又由于 $100$ 可以用 $1234$ 和 $567$ 表示出来，所以 $67$ 也可以用 $1234$ 和 $567$ 表示出来，即
$$
67=567-100 \times5=567-(1234-567 \times 2)=567 \times 3 - 1234。
$$
再再有
$$
100 \div 67 = 1 \dots 33
$$
类似地，$33$ 也可以用 $1234$ 和 $567$ 表示出来，即
$$
33=100-67=(1234-567\times2)-(567\times3-1234)=1234\times2-567\times5。
$$
再再再有
$$
67\div33=2\dots1
$$
那么 $1$ 也可以用 $1234$ 和 $567$ 来表示，即
$$
1=67-33\times2=(567\times3-1234)-2\times(1234\times2-567\times5)=13\times567-5\times1234=(a,b)。
$$
那么我们的目标就达成了，此时
$$
\begin{cases}
x=-5\\
y=13
\end{cases}。
$$
这里给出两种证明方法。
---
**第一种证明方法**：考虑模拟刚刚例子的过程，直接写出每次的余数，最后一个余数就是 $(a,b)$。
::::success[证明]{open}
证： $1^\circ$ 若 $b=0$，令
$$
x=sign(a),y=0
$$
且此时
$$
\gcd(a,b)=|a|
$$
则
$$
ax+by=a \times sign(a) + 0=|a|
$$
命题成立。
$2^\circ$ 若 $b \ne 0$，则根据刚刚的过程，
$$
\begin{cases}
a=bq_1+r_1 & 0 \le r_1 < b\\
b=r_1q_2+r_2 & 0 \le r_2 < r_1\\
r_1=r_2q_3+r_3 & 0 \le r_3 < r_2\\
\dots\\
r_{k-2}=r_{k-1}q_k+r_k & 0 \le r_k \le r_{k-1}\\
r_{k-1}=r_kq_{k+1}+0
\end{cases}
$$
则最后一个非 $0$ 余数即为 $(a,b)$，证毕。
::::
---
**第二种证明方法**：考虑构造一个集合
$$
S=\{ax+by \mid x,y\in \mathbb{Z},ax+by>0\}
$$
来证明集合中最小的元素就是 $(a,b)$。
::::success[证明]{open}
证：考虑以正整数为元素的集合
$$
S=\{ax+by \mid x,y\in \mathbb{Z},ax+by>0\}
$$
记 $S$ 中的最小元素 $d=ax_0+by_0$。
---
对于 $a,d$，设带余除法为
$$
a=dq+r
$$
则
$$
\begin{align*}
r&=a-dq\\
&=a-(ax_0+by_0)q\\
&=a(1-x_0q)+b(-y_0q)
\end{align*}
$$
若 $r>0$，则 $r \in S$，又由于 $d$ 是 $S$ 中的最小元素，与 $r<d$ 矛盾。
故 $r=0$，即 $d \mid a$。
---
类似地，对于 $b,d$，设带余除法为
$$
b=dk+p
$$
则
$$
\begin{align*}
p&=b-dk\\
&=b-(ax_0+by_0)k\\
&=a(-x_0k)+b(1-y_0k)
\end{align*}
$$
若 $p>0$，则 $p \in S$，又由于 $d$ 是 $S$ 中的最小元素，与 $p<d$ 矛盾。
故 $p=0$，即 $d \mid b$。
---
设 $c$ 为 $a,b$ 的任意公因数，即
$$
c \mid a,c \mid b
$$
因此
$$
c \mid ax_0+by_0
$$
即
$$
c \mid d
$$
故 $d$ 为 $a,b$ 的最大公因数。
即
$$
\exists x,y \in \mathbb{Z},ax+by=(a,b)。
$$
证毕。
::::
根据刚刚的证明，我们还知道 $(a,b)$，**是所有线性组合里最小的一个**，这个性质也被广泛使用。
### 例题一
::::info[题目]{open}
设 $n \ge m > 0$，求证：
$$
\frac{(m,n)}{n}C_n^m \in \mathbb{Z}^{+}。
$$
::::
注意到式子中有 $(m,n)$，可以应用裴蜀定理，把 $(m,n)$ 表示为 $mx+ny$，带入化简即可。
::::success[完整解答]{open}
证：由裴蜀定理，
$$
\exists x,y \in \mathbb{Z}^+,(m,n)=mx+ny
$$
则
$$
\begin{align*}
LHS&=\frac{mx+ny}{n}C_n^m\\
&=x \cdot\frac{m}{n} \cdot C_n^m+y\cdot C_n^m\\
&=x \cdot C_{n-1}^{m-1}+y\cdot C_n^m \in \mathbb{Z}^+。
\end{align*}
$$
证毕。
::::
### 例题二
::::info[题目]{open}
求证：
$$
\forall a,b \in \mathbb{Z}^+,(2^a-1,2^b-1)=2^{(a,b)}-1。
$$
::::
（未完待续）
### 例题二推论
::::info[推论一]{open}
若
$$
(x,y)=1,x \ne y
$$
设 $a,b$ 为正整数，则
$$
(x^a-y^a,x^b-y^b)=x^{(a,b)}-y^{(a,b)}。
$$
::::
这个推论即为例题二的一般形式。
---
::::info[推论二]{open}
若
$$
(x,y)=1,x \ne y
$$
设 $a,b$ 为正整数，则
$$
x^a-y^a \mid x^b-y^b \Leftrightarrow a \mid b。
$$
::::
这个推论结合了例题二和高次方差。
## 大公因与小公倍的性质
前面我们介绍了大公因与小公倍的应用——裴蜀定理，接下来我们来讲讲大公因与小公倍的性质。
---
::::info[性质1]{open}
设 $m$ 满足
$$
\forall 1\le i \le k,a_i \mid m
$$
则
$$
[a_1,a_2,\dots,a_k] \mid m。
$$
反之亦然。
::::
这个性质其实说的就是公倍数可以被最小公倍数整除。
::::success[证明]{open}
设
$$
m \div [a_1,a_2,\dots,a_k]=q\dots r
$$
因为
$$
\forall 1 \le i \le k,a_i \mid [a_1,a_2,\dots,a_k]
$$
且
$$
\forall 1 \le i \le k,a_i \mid m
$$
所以
$$
\forall 1 \le i \le k,a_i \mid m -[a_1,a_2,\dots,a_k]
$$
即
$$
\forall 1 \le i \le k,a_i \mid r
$$
而
$$
r < [a_1,a_2,\dots,a_k]
$$
故
$$
r=0
$$
即
$$
[a_1,a_2,\dots,a_k] \mid m。
$$
证毕。
::::
---
::::info[性质2]{open}
$$
[a_1,a_2,\dots,a_k]=[[a_1,a_2],a_3,\dots,a_k]
$$
::::
这个性质其实说的就是小公倍运算具有结合律。
::::success[证明]{open}
$$
\because a_1 \mid[a_1,a_2],[a_1,a_2] \mid RHS
$$
$$
\therefore a_1 \mid RHS
$$
同理，
$$
a_2 \mid RHS
$$
又由于
$$
\forall 3 \le i \le k,a_i \mid RHS
$$
$$
\therefore [a_1,a_2,\dots,a_k] \mid RHS
$$
即
$$
LHS \mid RHS
$$
---
$$
\because a_1 \mid LHS,a_2 \mid LHS
$$
$$
\therefore [a_1,a_2] \mid LHS
$$
又由于
$$
\forall 3 \le i \le k,a_i \mid LHS
$$
$$
\therefore [[a_1,a_2],a_3,\dots,a_k] \mid LHS
$$
即
$$
RHS \mid LHS
$$
---
故
$$
LHS=RHS
$$
证毕。
::::
---
::::info[性质3]{open}
$$
[ma_1,ma_2,\dots,ma_k]=m[a_1,a_2,\dots,a_k]
$$
::::
这个性质其实说的就是小公倍内的共同因数可以提出来。
::::success[证明]{open}
$$
\because \forall 1 \le i \le k,a_i \mid [a_1,a_2,\dots,a_k],m \mid m
$$
$$
\therefore \forall 1 \le i \le k,ma_i \mid m[a_1,a_2,\dots,a_k]
$$
$$
\therefore[ma_1,ma_2,\dots,ma_k] \mid m[a_1,a_2,\dots,a_k]
$$
即
$$
LHS \mid RHS
$$
---
$$
\because m \mid ma_1,ma_1 \mid LHS
$$
$$
\therefore m \mid LHS
$$
设
$$
LHS=md(d \in \mathbb{Z})
$$
$$
\because \forall 1 \le i \le k,ma_i \mid md
$$
$$
\therefore \forall 1 \le i \le k,a_i \mid d
$$
于是
$$
[a_1,a_2,\dots,a_k] \mid d
$$
$$
\therefore m[a_1,a_2,\dots,a_k] \mid md
$$
即
$$
RHS \mid LHS
$$
---
故
$$
LHS=RHS
$$
证毕。
::::
---
::::info[性质4]{open}
设 $d$ 满足
$$
\forall 1 \le i \le k,d \mid a_i
$$
则
$$
d \mid (a_1,a_2,\dots,a_k)。
$$
::::
这个性质其实说的就是公因数整除最大公因数。
::::success[证明]{open}
设 $d_1<d_2<\dots<d_l$ 为 $a_1,a_2,\dots,a_k$ 的所有公因数，则 $[d_1,d_2,\dots,d_l]$ 为 $a_1,a_2,\dots,a_k$ 的公因数。
$$
\therefore [d_1,d_2,\dots,d_l]=d_l
$$
即
$$
\forall 1 \le i \le l,d_i \mid d_l。
$$
证毕。
::::
---
::::info[性质5]{open}
$$
(ma_1,ma_2,\dots,ma_k)=m(a_1,a_2,\dots,a_k)
$$
::::
这个性质其实说的就是大公因内的共同因数可以提出来。
这个性质的证明可以参考性质 $2$ 的证明。
---
::::info[性质6]{open}
$$
(a_1,a_2,\dots,a_k)=((a_1,a_2),a_3,\dots,a_k)
$$
::::
这个性质说的其实就是大公因满足结合律。
这个性质的证明可以参考性质 $3$ 的证明。
---
::::info[性质7]{open}
对于若干个非 $0$ 整数 $a_1,a_2,\dots,a_k$，存在整数 $x_1,x_2,\dots,x_k$，使得
$$
\sum_{i=1}^{n}a_ix_i=(a_1,a_2,\dots,a_k)。
$$
::::
这个性质其实就是多元的裴蜀定理，可以参考裴蜀定理的证法 $2$ 进行证明。
下面我们来看一下性质的相关应用。
### 例题一
::::info[题目]{open}
求证：
$$
(a,uv)=(a,(a,u)v)。
$$
::::
暴力展开即可。
::::success[完整证明]{open}
证：
$$
\begin{align*}
(a,(a,u)v)&=(a,av,uv)\\
&=(a(1,v),uv)\\
&=(a,uv)。
\end{align*}
$$
证毕。
::::
### 例题二
::::info[题目]{open}
求证：
$$
(a,b)(u,v)=(au,av,bu,bv)。
$$
::::
类似地，暴力展开即可。
::::success[完整证明]{open}
证：
$$
\begin{align*}
(au,av,bu,bv)&=(a(u,v),b(u,v))\\
&=(a,b)(u,v)。
\end{align*}
$$
证毕。
::::
### 习题
::::info[习题]{open}
求证：
$$
(u,v)=1 \Rightarrow (a,uv)=(a,u)(a,v)。
$$
::::
## 互质的性质
互质有关与整除，大公因和小公倍的三个性质：
---
::::info[整除的互质可消性]{open}
$$
(a,b)=1,a \mid bc \Rightarrow a \mid c。
$$
::::
::::success[证明]{open}
证：由裴蜀定理，
$$
\exists x,y \in \mathbb{Z},ax+by=(a,b)=1。
$$
$$
\because a \mid ac,a \mid bc
$$
$$
\therefore a \mid ac \cdot x+bc \cdot y
$$
即
$$
a \mid c(ax+by)
$$
故
$$
a \mid c。
$$
证毕。
::::
---
::::info[大公因的互质可消性]{open}
$$
(a,b)=1 \Rightarrow (a,bc)=(a,c)。
$$
::::
::::success[证明]{open}
证：
$$
\because (a,b)=1
$$
$$
\begin{align*}
\therefore (a,c)&=(a,c(a,b))\\
&=(a,ac,bc)\\
&=(a(1,c),bc)\\
&=(a,bc)。
\end{align*}
$$
证毕。
::::
---
::::info[整除的互质可乘性（小公倍的互质可乘性）]{open}
$$
(a,b)=1,a \mid m,b \mid m
$$
$$
\Rightarrow ab \mid m,[a,b]=ab。
$$
::::
::::success[证明]{open}
证：
$$
\because a \mid m, b \mid m
$$
$$
\therefore ab \mid bm,ab \mid am。
$$
由裴蜀定理，
$$
\exists x,y \in \mathbb{Z},ax+by=(a,b)=1。
$$
$$
\therefore ab \mid y \cdot bm+x \cdot am
$$
即
$$
ab \mid m(ax+by)。
$$
故
$$
ab \mid m。
$$
证毕。
::::
---
这三个性质也尤为重要，也有很多相关应用。
### 例题一
::::info[题目]{open}
求证：
$$
(a,b)=1 \Rightarrow (ab,a \pm b)=1。
$$
::::
注意到
$$
(a,a \pm b)=(a,b)=1
$$
带入即可。
::::success[证明]{open}
证：
$$
\because (a,a \pm b) = (a,b) = 1
$$
$$
\therefore (ab,a \pm b)=(b,a \pm b)=(a,b)=1。
$$
证毕。
::::
### 例题二
::::info[题目]{open}
求证：
$$
(a,b)=1 \Rightarrow (a + b, a - b) = 1 \text{ 或 } 2。
$$
::::
先对左式进行辗转相除，再代入互质即可。
::::success[证明]{open}
证：
$$
\because (a+b,a-b)=(a+b,2b)
$$
且
$$
(a+b,b)=(a,b)=1
$$
故
$$
(a+b,a-b)=(a+b,2b)=(a+b,2)=1 \text{ 或 } 2。
$$
证毕。
::::
## 后记
**原创不易，点个赞再走吧。~~**
**求管理员通过 qwq。**
[更多精彩，关注我们的合集。](https://www.luogu.me/article/4y3zfcw5)