最后更新: 2023-11-09 18:34 查看: 180 次反馈纠错下载本文

最大公因数与最小公倍数

. 最大公因数

给定两个整数 $a, b$, 必有公共的因数, 叫做它们的公因数. 当 $a, b$ 不全为零时, 在有限个公因数中最大的一个叫做 $a, b$ 的最大公因数, 记作 $(a, b)$.
例如, -8 和 14 的全部公因数为 $1,-1,2,-2$, 最大的公因数为 2 , 所以

$$
(-8,14)=2 \text {. }
$$

如果 $a, b$ 的最大公因数为 1 , 那么称 $a, b$ 是互素的.
类似地, 我们可以定义三个或更多个整数的最大公因数和互素的概念. 将整数 $a, b$, $c$ 的最大公因数记作 $(a, b, c)$, 依此类推.
如何计算一组非零整数的最大公因数呢? 我们已经学习过一种算法 短除法.

我们发现, 用短除法求最大公因数有一定的局限性, 因为用它每进行一次操作必须事先观察到一个大于 1 的公因数, 而这一点有时难以做到. 特别是求两个较大整数的公因数时, 这一点显得更为突出.

如何求 $(1840,667) ?$ 一个自然的考虑是把 1840,667 通过适当的方式都变小, 变小后, 公因数就容易求出了. 如何变小呢? 看下面的问题.
如果 $b$ 除 $a$ 的余数为 $r$, 那么 $(a, b)$ 是否等于 $(b, r)$ ?
事实上, 若 $d$ 为 $a, b$ 的公因数, 即 $d|a, d| b$, 则 $d \mid a-b q=r$, 从而 $d$ 为 $b, r$ 的公因数. 同理可证, $r, b$ 的公因数也是 $a, b$ 的公因数. 因此, $a, b$ 公因数的集合与 $r, b$公因数的集合相同, 从而它们的最大公因数相等, 即 $(a, b)=(b, r)$.
按照这种思路, 我们来求 $(1840,667)$.
因为 $1840=667 \times 2+506$, 所以 $(1840,667)=(667,506)$; 又因为 $667=506 \times 1+$

161 , 所以 $(667,506)=(506,161)$; 又因为 $506=161 \times 3+23$, 所以 $(506,161)=(161$, $23)$, 而 $(161,23)=23$. 因此

$$
(1840,667)=23 \text {. }
$$

这种求最大公因数的方法, 叫做辗转相除法- - 它是一种古老而有效的算法. 下面,我们给出辗转相除法的一般形式.

设 $a$ 和 $b$ 为任意两个整数, 且 $b \neq 0$. 应用带余除法, 以 $b$ 除 $a$, 得商 $q_1$ 和余数 $r_1$. 如果 $r_1 \neq 0$, 那么再以 $r_1$ 除 $b$, 得商 $q_2$ 和余数 $r_2$. 如果 $r_2 \neq 0$, 再以 $r_2$ 除 $r_1$, 如此继续下去, $r_i(i=1,2, \cdots)$ 越来越小, 有限次这种除法后, 必然得到一个余数 $r_n \neq 0$, 它整除前一个余数 $r_{n-1}$. 于是, 我们有:

$$
\begin{aligned}
& a=b q_1+r_1, \\
& b=r_1 q_2+r_2, \\
& r_1=r_2 q_3+r_3, \\
& \cdots \cdots \\
& r_{n-2}=r_{n-1} q_n+r_n, \\
& r_{n-1}=r_n q_{n+1} .
\end{aligned}
$$

即

$$
(a, b)=\left(b, r_1\right)=\left(r_1, r_2\right)=\cdots=\left(r_{n-1}, r_n\right)=\left(0, r_n\right)=r_n .
$$

也就是说, $r_n$ 是 $a, b$ 的最大公因数.

下面探讨三个整数的最大公因数的求法.

探究

1. 自己列举几组整数 $a, b, c$, 计算并比较 $(a, b, c),((a, b), c)$, 从中你能发现什么规律?
2. 求三个整数的最大公因数与求两个整数的最大公因数之间有什么联系?

我们发现, 无论怎样选取 $a, b, c$, 恒有

$$
(a, b, c)=((a, b), c) .
$$

这表明, 求三个整数的最大公因数, 总可以转化为求两次两个整数的最大公因数.
对于多于三个整数的最大公因数, 我们也有类似的结论.
关于最大公因数, 有一条重要的性质. 这条性质在求解一次同余方程和不定方程时经常要用到.
设整数 $a, b$ 不同时为零, 则存在一对整数 $m, n$, 使得 $(a, b)=a m+b n$.
你能用轵转相除法证明上述性质吗?
下面我们给出它的证明.
证明: 不妨设 $b>0$, 用 $b$ 除 $a$, 则

$$
a=b q_1+r_1\left(0 \leqslant r_1<b\right) .
$$

因为 $(a, b)=\left(b, r_1\right)$, 若 $r_1=0$, 则

$$
(a, b)=\left(b, r_1\right)=b \text {. }
$$

此时取 $m=0, n=1$, 即有

$$
(a, b)=b=a \times 0+b \times 1 .
$$

若 $r_1 \neq 0$, 用 $r_1$ 除 $b$, 则

$$
b=r_1 q_2+r_2\left(0 \leqslant r_2<r_1\right),
$$

且

$$
\left(b, r_1\right)=\left(r_1, r_2\right) \text {. }
$$

若 $r_2=0$, 则

$$
(a, b)=\left(r_1, r_2\right)=r_1=a-b q_1 .
$$

此时取 $m=1, n=-q_1$, 即有

$$
(a, b)=r_1=a \times 1+b \times\left(-q_1\right) .
$$

若 $r_2 \neq 0$, 用 $r_2$ 除 $r_1$, 则
且

$$
\begin{gathered}
r_1=r_2 q_3+r_3\left(0 \leqslant r_3<r_2\right), \\
\left(r_1, r_2\right)=\left(r_2, r_3\right) .
\end{gathered}
$$

若 $r_3=0$, 则

$$
\begin{aligned}
(a, b) & =\left(r_2, r_3\right)=r_2=b-r_1 q_2=b-\left(a-b q_1\right) q_2 \\
& =a \times\left(-q_2\right)+b \times\left(1+q_1 q_2\right) .
\end{aligned}
$$

此时取 $m=-q_2, n=1+q_1 q_2$, 即有

$$
(a, b)=a \times\left(-q_2\right)+b \times\left(1+q_1 q_2\right) .
$$

若 $r_3 \neq 0$, 再用 $r_3$ 除 $r_2$, 依次类推.
由上可知, 这样的 $m$ 和 $n$ 是存在的.
这个性质对多于两个整数情形仍然成立, 由它还可以推出整除的一条重要性质.
若 $a \mid b c$, 且 $(a, b)=1$, 则 $a \mid c$.

下面我们给出它的证明.
证明: 因为 $(a, b)=1$,
所以存在一对整数 $m, n$, 使得 $a m+b n=1$.
于是 $(a c) m+(b c) n=c$.
又因为 $a|a c, a| b c$,
所以 $a \mid(a c) m+(b c) n$, 即 $a \mid c$.
由整除的上述性质, 我们可以得出素数的一条重要性质.
设 $p$ 为素数, 若 $p \mid a b$, 则 $p \mid a$, 或 $p \mid b$.

下面我们给出它的证明.
证明: 因为 $p$ 为素数, 其正因数只有 $1, p$, 所以

$$
(p, a)=1 \text {, 或 }(p, a)=p .
$$

若 $(p, a)=1$, 则由上面整除的性质知

$$
p \mid b .
$$

若 $(p, a)=p$, 则 $p \mid a$.
素数的这条性质可以推广到一般情形: 设 $p$ 为素数, 若 $p \mid a_1 a_2 \cdots a_k$, 则存在 $a_i(1 \leqslant$ $\leqslant k)$, 使得 $p \mid a_i$.
你能给出它的证明吗?

**2. 最小公倍数**
甲、乙两个齿轮互相啮合, 齿数分别为 84,36 , 在转动过程中同时啮合的两齿到下次再同时啮合，甲、乙两个齿轮分别转过多少圈?

这个问题的实质是, 求出一个最小正整数, 它同时为 84,36 的倍数.
事实上, 任给两个非零整数 $a, b$, 一定存在一个整数, 它同时为 $a, b$ 的倍数, 这个倍数叫做 $a, b$ 的公倍数. 例如, $|a b|$ 就是 $a, b$ 的一个公倍数.
我们把 $a, b$ 的最小的正公倍数叫做 $a, b$ 的最小公倍数, 记作 $[a, b]$.
例如, $8,-6$ 的公倍数为 $24,-24,48,-48,72,-72, \cdots$ 其中最小的正公倍数为 24 , 因此 $[8,-6]=24$.

类似地, 我们还可以定义三个非零整数或更多个非零整数的最小公倍数的概念, 将非零整数 $a, b$ 和 $c$ 的最小公倍数记作 $[a, b, c]$, 依此类推.
下面我们证明两个非零整数 $a, b$ 的最小公倍数 $[a, b]$ 一定整除 $a, b$ 的公倍数.
证明：设 $[a, b]=m, n$ 为 $a, b$ 的任意一个公倍数.
对 $n, m$ 用带余除法: $n=m q+r(0 \leqslant r<m)$.
假设 $m$ 不能整除 $n$, 则 $r>0$.
由 $a|m, b| m, a|n, b| n$, 得$a|n-m q=r, b| n-m q=r$,
所以 $r$ 也是 $a, b$ 的一个正公倍数, 而 $r<m$, 这与 $m=[a, b]$ 矛盾.
因此, $m \mid n$.
我们发现, $(a, b),[a, b]$ 和 $a b$ 之间存在下面的关系:

$$
(a, b)[a, b]=|a b| .
$$

上述关系的证明此处略.
由上述关系可知, 可以由两个非零整数乘积的绝对值除以它们的最大公因数求得它们的最小公倍数.
例 4 求 $[375,105]$ 的值.
解: 因为 $375=105 \times 3+60$,

$$
\begin{aligned}
& 105=60 \times 1+45, \\
& 60=45 \times 1+15, \\
& 45=15 \times 3,
\end{aligned}
$$

所以

$$
(375,105)=15 \text {. }
$$

于是

$$
[375,105]=\frac{375 \times 105}{(375,105)}=2625

上一篇：素数及其判别法

下一篇：算术基本定理

本文对您是否有用？有用 (0) 无用 (0)

打赏作者

0 条评论写评论

更多笔记