当前位置：首页 > news >正文

【基础数学二】整除，最大公约数约数，最小公倍数

news 来源：原创 2024/12/9 14:29:26

整除

在数论中，一个整数 $a$ 能够被另一个整数 $d$ 整除，记做 $d ∣ a$ 。

整除的性质：

如果 $d ∣ a$ ，则对于任意整数 $k$ 有 $d ∣ ka$ 。
如果 $d ∣ a$ 并且 $d ∣ b$ ，则 $d ∣ (a \pm b)$ 。
如果 $b ∣ a$ 并且 $a ∣ b$ ，则 $a = b$ 。

约数&倍数

若整数 $d$ 能整除整数 $a$ (记为 $d ∣ a$ ）且 $d > 0$ ，则称 $d$ 是 $a$ 的约数（Divisor）。一个整数 $a$ 的约数最小为 $1$ ，最大为 $∣ a ∣$ ，比如 $20$ 的约数有 $1$ 、 $2$ 、 $4$ 、 $5$ 、 $10$ 和 $20$ 。

若 $d ∣ a$ ，则称 $a$ 是 $d$ 的倍数（Multiple）。即存在整数 $k$ ，使得 $a = k d$ ，例如 $20$ 是 $1$ 、 $2$ 、 $4$ 、 $5$ 、 $10$ 、 $20$ 的倍数。

公约数&最大公约数

如果 $d$ 是 $a$ 的约数也是 $b$ 的约数，则 $d$ 是 $a$ 与 $b$ 的公约数。

最大公约数顾名思义就是，所有公约数中最大的那个。

一般地，将 $a$ 和 $b$ 的最大公约数记为 $g c d (a, b)$ 。

举个例子， $g c d (15, 20) = 5$ ， $g c d (1, 20) = 1$ ， $gcd(0, 20) = 20 $。

需要特别注意， $g c d (0, 0) = 0$ 。

最大公约数具有以下性质：

$g c d (a, ka) = ∣ a ∣$ 。
对于任意整数 $a$ 与 $b$ ，如果 $d ∣ a$ 且 $d ∣ b$ ，则 $d ∣ g c d (a, b)$ 。
对所有整数 $a$ 和 $b$ 以及任意非负整数 $n$ ， $g c d (an, bn) = n g c d (a, b)$ 。
对所有正整数 $d$ ， $a$ 和 $b$ ，如果 $d ∣ ab$ 并且 $g c d (a, b) = 1$ ，则 $d ∣ b$ 。
如果 $q$ 和 $r$ 是 $a$ 除以 $b$ 的商和余数，即 $a = b * q + r$ ，则 $g c d (a, b) = g c d (b, r)$ 。

公倍数&最小公倍数

如果 $m$ 是 $a$ 的倍数并且也是 $b$ 的倍数，则 $m$ 是 $a$ 与 $b$ 的公倍数。

最小公倍数顾名思义，就是所有的公倍数中最小的那个。

一般地，将 $a$ 和 $b$ 最小公倍数记为 $l c m (a, b)$ 。

举个例子， $l c m (8, 12) = 24$ ， $l c m (1, 12) = 12$ ， $l c m (0, 12) = 0$ ， $l c m (0, 0) = 0$ 。

最小公倍数的性质：

$l c m (a, b) = a * b / g c d (a, b)$ 。

求最大公约数&最小公倍数

在编程时，我们一般使用 辗转相除法 来求两个数的最大公约数，也就是直接利用第五个性质。

如果 $q$ 和 $r$ 是 $a$ 除以 $b$ 的商和余数，即 $a = b * q + r$ ，则 $g c d (a, b) = g c d (b, r)$ 。

举个例子：
$g c d (1001, 767)$
$= g c d (767, 234)$
$= g c d (234, 65)$
$= g c d (65, 39)$
$= g c d (39, 26)$
$= g c d (13, 0)$
$= g c d (26, 13)$
$= 13$

求最大公约数：

// 辗转相除法求最大公约数
int gcd(int a, int b) {return !b ? a : gcd(b, a % b);
}

求最小公倍数：

// 利用最大公约数求最小公倍数
int lcm(int a, int b) {return a * b == 0 ? 0 : a * b / gcd(a, b);
}

求 $a^b mod\ n$ :

// 求 a mod n
int qmi(int a, int b, int n) {int t = 1;int y = a;while (b > 0) {if (b % 2 == 1)t = (t * y) % n;y = (y * y) % n;b /= 2;}return t;
}

整除

约数&倍数

公约数&最大公约数

公倍数&最小公倍数

求最大公约数&最小公倍数

相关文章：