最大公约数与最小公倍数
发表于 2018-09-06 |更新于 2018-09-06 |基础数论实现
1.设 $a$ 和 $b$ 是两个不全为 $0$ 的整数,称 $a$ 与 $b$ 的公因子中最大的为 $a$ 与 $b$ 的最大公因子,或最大公约数,记作 $gcd(a,b)$.
2.设 $a$ 和 $b$ 是两个非零整数,称 $a$ 与 $b$ 的最小的正公倍数为 $a$ 与 $b$ 的最小公倍数,记作 $lcm(a,b)$.
(1) 若 $a|m,b|m$,则 $lcm(a,b)|m$.
(2) 若 $d|a,d|b$,则 $d|gcd(a,b)$.
(3) $lcm(a,b)=\frac{ab}{gcd(a,b