最后更新: 2025-10-15 09:41 查看: 496 次纠错评论(0) 课件开VIP

最大公因数GCD

## 最大公因数(Greatest Common Divisor, GCD)

给定两个整数 $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)$, 依此类推.

> 从上面可以看到，如果$k$是公因数，那么$-k$也是他的公因数，所以，只要讨论正数即可。

## 辗转相除法
如何计算一组非零整数的最大公因数呢? 我们已经学习过一种算法 **短除法**.

短除符号就是除号倒过来。短除就是在除法中写除数的地方写两个数共有的质因数，然后落下两个数被公有质因数整除的商，之后再除，以此类推，直到结果互质为止（两个数互质）。

而在用短除计算公倍数数时，对其中任意两个数存在的因数都要算出，其它没有这个因数的数则原样落下。直到剩下每两个都是互质关系。

![图片](/uploads/2025-06/54c50e.jpg){width=200px}

我们发现, 用短除法求最大公因数有一定的局限性, 因为用它每进行一次操作必须事先观察到一个大于 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$ 的最大公因数.

下面是计算机代码的实现

使用递归实现辗转相除法求最大公约数
  参数: a, b: 两个正整数
  返回:最大公约数
    
``` 
def gcd_recursive(a, b):   
    if b == 0:
        return a
    return gcd_recursive(b, a % b) 
```

测试
``` 
print(gcd_recursive(48, 18))  # 输出: 6
print(gcd_recursive(56, 42))  # 输出: 14
```

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

探究

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$.
你能给出它的证明吗?

其他版本
【高等代数】整除性理论与理想

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：素数及其判别法

下一篇：最小公倍数LCM

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