整除的进一步性质与最小公倍数

最大公因数的重要性质（定理1，推论1，命题1，推论2）

定理1

若$a,b\in {\mathbb{Z}}_{+}$,则：

$$Q_{k}a-P_{k}b=(-1{)}^{k-1}{r}_k(k=1,2,\dots ,n)$$

其中

$$P_0=1,P_1=q_1,P_k=q_k{P}_{k-1}+P_{k-2}$$

$Q_0=0,Q_1=1,Q_k=q_k{Q}_{k-1}+Q_{k-2}(k=2,3,\dots ,n)$

引入定理1的目的是为了给出下面的推论1和推论2，可以将 { P i } i = 0 n \{P_i\}_{i=0}^{n} {Pi​}i=0n​和 { Q i } i = 0 n \{Q_i\}_{i=0}^{n} {Qi​}i=0n​看成是数列，它是一个重要的工具，满足第一个式子。

先说明一下$q$是什么

• $a=b{q}_1+r(0<r_1<b)$
• $b=r_1{q}_2+r_2(0<r_2<r_1)$
• $\dots$
• $r_{k-1}=r_k{q}_{k+1}+r_{k+1}(0<r_{k+1}<r_k)$
• $\dots$
• $r_{n-2}=r_{n-1}{q}_n+r_n(0<r_n<r_{n-1})$
• $r_{n-1}=r_n{q}_{n+1}+r_{n+1}(r_{n+1}=0)$

当$r_{n+1}=0$的时候带余除法就结束了。 上面的式子的$q_i$可以构成一个数列 { q i } i = 0 n + 1 \{q_i\}_{i=0}^{n+1} {qi​}i=0n+1​ 这就是来源

证明可以用第二数学归纳法。

推论1（裴蜀定理）

若$(a,b)=d$,则存在$s,t\in \mathbb{Z}$,有$as+bt=d$.

下面用上面那个结论来证明一下之前我们用到过的裴蜀（贝祖）定理

我们只考虑$a>0,b>0$的情况，其余情况可以转换到这上面来

由定理1

$Q_{n}a-P_{n}b=(-1{)}^{n-1}{r}_n$

等式两边同时乘以$(-1{)}^{n-1}$

$$r_n=(-1{)}^{n-1}{Q}_{n}a-(-1{)}^{n-1}{P}_{n}b$$

取$s=(-1{)}^{n-1}{Q}_n,t=(-1{)}^n{P}_n$即可

下面看一个例子

例1

设$a=42823,b=6409$

1. 求$gcd(a,b)$
2. 找到合适的$s,t$，使得$as+bt=gcd(a,b)$

42823=6409x6(q1)+4369(r1)6409=4369x1(q2)+2040(r2)4369=2040x2(q3)+289(r3)2040= 289x7(q4)+17(r4)289=17x17(q5)+0
所以(a,b)=d=r4=17 这是第一问

• 我们从定理1的递推公式出发去找$s,t$
• $d=r_4,Q_{4}a-P4b=-r_4$
• 现在的任务就是计算$Q_4$和$P_4$
• $P_0=1,P_1=q_1=6,P_k=q_k{P}_{k-1}+P_{k-2}$
• $Q_0=0,Q_1=1,Q_k=q_k{Q}_{k-1}+Q_{k-2}$
• 根据初始条件和公式可以算出
• $Q_4=22,P_4=147$
• 所以$s=-22,t=147$

于是我们找到了$-22\times 42823+147\times 6409=17=gcd(42823,6409)$

那么问题来了，推论1的逆命题是否是正确的，我们先写出来

若果存在整数$s,t,as+bt=d$,则$gcd(a,b)=d$

这个命题是否正确呢？ 这显然是不对的，随意举出一个反例

$a=2,b=3,s=t=1$ 则$as+bt=5$显然$gcd(2,3)\ne 5$

这个逆命题适当加一些条件就正确了，见命题1

命题1

设$a,b,d\in \mathbb{Z},d>0$,若存在$s,t\in \mathbb{Z}$，有$as+bt=d$,且$d$是$a,b$的公因数，则$(a,b)=d$

注意加粗的，我们只增加了一个条件，就能够推出$(a,b)=d$了

证明：

• 因为$d$是$a,b$的公因数，要证$(a,b)=d$只需要证$d$是最大的一个公因数即可
• 任取$d^{\prime }$是$a,b$的公因数，则$d^{\prime }\mid a,d^{\prime }\mid b\Rightarrow d^{\prime }\mid as+bt=d>0$
• 由命题 $b\mid a,a>0\Rightarrow b\le a$
• 故$d^{\prime }\le d$

由上一节的注解2可得知$(a,b)=d$。 这个命题很有用的 下面的推论2就要用到

推论2

设$a,b\in \mathbb{Z},$则$(a,b)=1$当且仅当存在$s,t\in \mathbb{Z}$,有$as+bt=1$

证明：

• $"=>"$: $(a,b)=1$ 由推论一可知是存在这样的$s,t$的
• $"\Leftarrow ":$ 由命题1可知1一定是公因数，故证毕

最大公因数的化简性质（定理2，推论3，推论4）

定理2

设$a,b,c\in \mathbb{Z}$且$(a,c)=1$,则：

1. $ab,c$与$b,c$有相同的公约数;
2. $(ab,c)=(b,c)$

这里$b,c$中至少有一个不为零。

这个是推论2的一个具体的应用

证： 其实证明1就可以了，有相同的公因数的话一定有相同的最大公因数

• 任取$k$是$ab,c$的公因数，然后我们证明$k$是$b,c$的公因数就行了

• 由推论2，$\exists s,t\in \mathbb{Z}$,有$as+ct=1\Rightarrow b(as+ct)=b=(abs)+c(bt)$

• $k\mid ad,k\mid c$ 所以$k$一定整除它俩的线性组合，故 $k\mid b$ 从而$k$是$b,c$的公因数

• 反过来 对于任意的$k$是$b,c$的公因数$k\mid b\Rightarrow k\mid ba,$又$k\mid c$所以$k$是$ab,c$的公因数

• 综上可知$ab,c$与$b,c$有相同的公约数。

举个例子$(12,14)=(3\times 4,14)=(4,14)=(14,4)=(7\times 2,4)=(2,4)=2$

这其实也是求最大公约数的一种化简的方法吧。

推论3

若$(a,c)=1,c\mid ab$,则$c\mid b$

这个我们之前证过（用的是推论1）。现在我们用定理2来证明

证：

$(b,c)=(ab,c)=\left|c\right|$ 从而$\left|c\right|\mid b$ 从而$c\mid b$

推论4

设$a_1,a_2,\dots ,a_n,b_1,b_2,\dots ,b_m$是两组整数，如果前一组的任意一个数与后一组中任意一个都互质，则$a_1{a}_2\dots a_n$与$b_1{b}_2\dots b_m$互质

由题设 $\forall i=1,2,...,m:$

$$1=(a_i,b_i)\stackrel{定理2}{=}(a_1{a}_2,b_i)\stackrel{定理2}{=}(a_1{a}_2{a}_3,b_i)=\cdots =(\underline{a_1{a}_2\cdots a_n},b_i).$$

$$1=(a_1{a}_2\cdots a_n,b_i)\stackrel{定理2}{=}(a_1{a}_2\cdots a_n,b_1{b}_2)\stackrel{定理2}{=}\cdots \stackrel{定理2}{=}(a_1\cdots a_n,b_1{b}_2\cdots b_m)$$

最小公倍数的定义和简单性质（定义1，例2，注解5，定理3）

定义1

若$e$是所有$a_1,a_2,\dots ,a_n$的倍数，则称$e$为$a_1,a_2,\dots ,a_n$的公倍数，在所有公倍数中的最小正数叫做$a_1,a_2,\dots ,a_n$的最小公倍数，记为$[a_1,a_2,\dots ,a_n]$或者$lcm(a_1,a_2,\dots ,a_n)$。

例2

计算下列每组数的最小公倍数

1. $a=12,b=18$
2. $a=12,b=15,c=6$

显然一个是$36$一个是$60$

最简单的一个计算最小公倍数的方法是遍历最大的那个数的倍数，如何看是否能整除每一个数

还有一个公式$ab=gcd(a,b)lcm(a,b)$即两个数的乘积等于它们的最小公倍数乘以最大公因数

注解5

$[a_1,a_2,\dots ,a_n]=e$当且仅当

1. $a_i\mid e(i=1,2,\dots ,n);$
2. 若$a_i\mid e^{\prime }$，则$e^{\prime }\le e$.

这个定义和最大公约数的很像 那么我们试想是否会有推广，当然是有的

定理3

$[a_1,a_2,\dots ,a_n]=[\left|a_1\right|,\left|a_2\right|,\dots ,\left|a_n\right|].$

这个和最大公因数的性质是类似的。

这个告诉我们可以直接全部转化为正数来求解。

最小公倍数的计算方法（定理4，定理5）

定理4

设$a,b\in {\mathbb{Z}}_{+}$,

1. $a,b$所有公倍数就是$[a,b]$的所有倍数
2. $[a,b]=\frac{ab}{(a,b)}$ 或$ab=[a,b](a,b)$,特别地，若$(a,b)=1$，则$ab=[a,b]$

这个就是我们刚才说到的式子

这个方法给出了计算最小公倍数的方法。

例3

计算下列数的最小公倍数

1. $a=51,-45$
2. $a=-1250,b=35$

全部转化为正数计算即可，怎么来都行

定理5

若$[a_1,a_2,\dots ,a_n]=m,[a_1,a_2]=m_2,[m_2,a_3]=m_3,\dots ,[m_{n-1},a_n]=m_n,$则$m=m_n$

这个定理跟最大公因数的那个性质也很像，就不证了。

定义2

设$n\in {\mathbb{Z}}_{+},a_0,a_1,a_2,\dots ,a_n\in \mathbb{R}(或某一数域)$,$a_n\ne 0$,则称

$$P(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$$

为一个$n$次多项式，简称多项式。

命题2

设 $P(x),M(x)$ 是任意两个多项式，$P(x)$ 的次数大于 $M(x)$ 的次数，则存在唯一的一对多项式 $Q(x),R(x)$，使得 $$P(x)=M(x)Q(x)+R(x)$$ 其中 $R(x)$ 的次数小于 $M(x)$ 的次数。（多项式的带余除法）

这个的详细证明参考高等代数。本章所讨论的概念，算法，整数的整除性，因数，倍数的各种性质以及下一节的算术基本定理都可以不困难地用类似的手法对多项式证明成立。第三，四章也有很多性质对多项式也相应成立。