GCD与LCM的关系

Question

下面的关系只适用于两个(3，12)数字，当用于三个数字(3,12,10)时，它无法产生正确的答案。只是想知道这是我的理解，还是只针对两个数字，对我来说欧几里得算法也是如此。

LCM(a, b) = (a x b) / GCD(a,b) or GCD(a,b) = (a x b) / LCM(a, b) 

Answer 1

的类似公式

LCM(a, b) = (a x b) / GCD(a,b) or GCD(a,b) = (a x b) / LCM(a, b) 

使用三个变量根本不是有效的，正如您的示例(3，12，10)所示。

这三个数字的乘积是360。GCD是1，LCM是60。

Answer 2

通过寻找模式来尝试和简化/泛化事物是我们的共同天性。然而，尽管尝试通过将其扩展到n个变量的一般情况来应用该想法可能是直观的，但它在这种情况下不起作用。我将尝试打破公式背后的推理。

首先，我们必须理解LCM(x，y) * GCD(x，y) =x*y的公式是如何得出的。要找到LCM或GCD，一种方法是将每个数字分解为它们的质因数。设x= 84，y= 30

X= 2*2*3*7 = (2*3)*2*7

Y= 2*3*5 = (2*3)*5

括号中的部分是通用部分。所以我们说ok，2*3，也就是6应该能够同时除以x和y，并称之为最大公约数。请注意，只有2或3也是x和y的公约数，但不是最大的公约数。

为了找到最小公倍数，我们取GCD并将其乘以留下的所有数字。所以我们的LCM是(2*3)*2*7*5 = 420。我不是在描述这背后的直觉，因为它很简单，也不直接相关。

因此，如果将x和y相乘，得到84*30 = ( 2 *3*2*7)*(2*3*5) = (2*3)*((2*3)*2*7*5) = GCD(x，y)*LCM(x，y) = (2*3)*(2*3)*(2*7*5) =公共部分的2次方，因为它在两个数字中重复*所有数字中剩余因子的其余部分。

现在来看你的问题，如果你再取一个变量z= 18 = (2*3)*3，所有3个数字的GCD是公共部分(2*3)，即6，LCM是(2*3)*2*7*5*3，不管是什么。

现在x*y*z = (2* 3 )*(2*3)*(2*3)*(2*7*5*3) =公共部分的3次方，因为它在所有3个数字中重复*所有数字中剩余的因子。但是，如果将GCD和LCM相乘，则只能得到(2*3)*((2*3)*2*7*5*3) = (2*3)*(2*3)*(2*7*5*3)，即只考虑公共部分两次，而不是三次。

然而，当一些数字之间的一些因素(不是全部，即不能包括在GCD中)是常见的时，也可能是这种情况。在n个变量的一般情况下，GDD(x1，x2，...xn) = c1c2..ck，其中每个ci 1<=i<=k在所有数字中存在一次。LCM((x1，x2，...xn) = GCD(x1，x2，...xn) * ((h(p1) * h(p2) * ...h(pl))，其中每个pj，1<=j<=l是不属于GCD的剩余因子列表中的质数，h( pi )是其中任何一个中存在的pi的最高幂。

现在，当我们将n个数字的LCM和GCD相乘时，除了在任何超过两倍的GCD因子上丢失外，我们还丢失了某些数字之间部分通用的因子，并且只能找到乘以GCD的最高幂的结果。