我们知道,两个数的最大公约数可以用过辗转相除法获得,而两个数的最小公倍数可以通过最大公约数求出。即:
证明:设 \(a = k_1 d,\; b = k_2 d,\; d = \gcd(a,b)\),因为 \(\operatorname {lcm}(a,b) = k_1 \times k_2 \times d\)。所以 \(\operatorname {lcm}(a,b) = ab \div d\)。
这是最常见的情况,只涉及两个数那如果涉及多个数该怎么办。
多个数的最大公约数
首先我们知道,每个数 \(x\) 都可以分解成一堆质数相乘的形式。而最大公约数,就是所有数都有的质数的乘积而已,即 \(d = \prod_{i = 1}^k p_i^{\min(a_i, b_i,c_i)}\)。
所以,每多一个数,这个最大公约数的限制就会增多,设 \(d = \gcd(a,b,c), d_1 = \gcd(a,b)\),那么自然有 \(d | d_1\)(\(d_1\) 的限制少于 \(d\)),即 \(d\) 所含的质数 \(d_1\) 里面一定也含有,因此可以得到:\(\gcd(a,b,c) = \gcd(\gcd(a,b),c)\)。
而这就是我们最常用的求多个数最大约数的方式,即:\(a,b,c\) 的最大公约数等于 \(a,b\) 的最大公约数和 \(c\) 的最大公约数。\(\gcd(a,b,c) = \gcd(\gcd(a,b),c)\)。
或者从另一方面想,因为
因此:\(\gcd(a,b,c) = \gcd(\gcd(a,b),c)\)。这样可能更容易理解。
多个数的最小公倍数
和最小公约数不同,最小公倍数不是每个数都共有的质数乘积。而是每个数具有质数最大次数的乘积,即:$$d = \prod_{i = 1}^k p_i^{\max(a_i, b_i,c_i)}$$可以看出最小公倍数和最大公约数是正好反着来的。
根据这个原理来说,因为:
所以 \(\operatorname {lcm}(a,b,c) = \operatorname {lcm}(\operatorname {lcm}(a,b), c)\)。而我们又知道 \(\operatorname {lcm}(a,b) = ab \div d\),所以可以 \(\gcd\) 来求出 \(\operatorname {lcm}\)。这就是多个数的最小公倍数的处理办法。