数论03_最大公约数_gcd

吴老师

2026-08-23 13:28:16

发布于：广东

7阅读

0回复

0点赞

03 最大公约数 gcd

学习目标

理解 $\gcd(a,b)$ 、互质，以及“互质为什么决定逆元是否存在”。

1. 最大公约数

12 的因数有 $1,2,3,4,6,12$ ，18 的因数有 $1,2,3,6,9,18$ 。

最大公共因数是 6，所以：

$\gcd(12,18)=6$

2. 什么叫互质

若 $\gcd(a,b)=1$ ，称 $a,b$ 互质。

注意：互质不代表两个数都必须是素数。例如 $\gcd(8,15)=1$ 。

3. 素数的一个重要性质

若 $p$ 是素数，且 $1\le a<p$ ，那么一定有：

$\gcd(a,p)=1$

因为 $p$ 的正因数只有 1 和 $p$ ，而 $a<p$ 。

4. 为什么 gcd 和逆元有关

后面会证明：

$a$ 在模 $m$ 下存在乘法逆元，当且仅当 $\gcd(a,m)=1$ 。

因此求 gcd 其实是在判断“能不能做模意义下的除法”。

5. 基本性质

$\gcd(a,b)=\gcd(b,a)$

$\gcd(a,0)=|a|$

若 $d=\gcd(a,b)$ ，则 $d\mid a$ 且 $d\mid b$ 。

6. 暴力做法

int gcd_slow(int a, int b) {
    for (int d = min(a, b); d >= 1; d--)
        if (a % d == 0 && b % d == 0)
            return d;
    return 1;
}

下一节会学习更快的欧几里得算法。

7. 小练习

$\gcd(24,36)$
8 和 21 互质吗？
若 $p=17$ 且 $1\le a<17$ ， $\gcd(a,17)$ 是多少？

答案

12
互质
1

有帮助，赞一个

去预览

0/2000

这里空空如也