GCD与LCM关系
以下关系仅适用于两个 (3, 12) 数字，当用于三个数字 (3,12,10) 时，它无法产生正确的答案。只是想知道这是我的理解还是仅适用于两个数字，对我来说欧几里得算法也是如此。
LCM(a, b) = (a x b) / GCD(a,b) or GCD(a,b) = (a x b) / LCM(a, b)
The following relation works only for two (3, 12) numbers, it fails to produce the right answer when used for three numbers (3,12,10) . Just wondering if is it my understanding or it is just for two numbers and for me same is true for Euclid algorithm as well.
LCM(a, b) = (a x b) / GCD(a,b) or GCD(a,b) = (a x b) / LCM(a, b)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
具有三个变量的类似公式
根本无效，正如 (3, 12, 10) 的示例所示。
这三个数字的乘积是 360。GCD 是 1。LCM 是 60。
The analogous formulas to
with three variables are simply not valid, as your example with (3, 12, 10) shows readily.
The product of these three numbers is 360. The GCD is 1. The LCM is 60.
通过寻找模式来尝试简化/概括事物是我们的共同本性。然而，虽然我可能很直观地尝试将这个想法扩展到 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
括号内部分为公共部分。所以我们说好吧，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(x[1],x[2],...x[n]) = c[1]c[2]..c[k]其中每个 c[i] 1<=i<=k 在所有数字中都存在一次。 LCM((x[1],x[2],...x[n]) = GCD(x[1],x[2],...x[n]) * ((h(p[1] ]) * h(p[2]) * ... h(p[l])) 其中每个 p[j], 1<=j<=l 是剩余因子列表中不属于的素数GCD 和 h(p[i]) 是其中任何一个中存在的 p[i] 的最高幂
现在，当我们将 n 个数的 LCM 和 GCD 相乘时，除了失去任何超过两倍的 GCD 因子。也松散了一些数字之间部分共有的因子，并且只能找到存在的最高幂乘以 GCD 的结果。
It is our common nature to try and simplify/generalize things by finding patterns. However, though it might me intuitive to try to apply the idea by extending it to the general case of n variables, it doesn't work in this case. I'll try to break up the reasoning behind the formula .
First we must understand how the formula of LCM(x,y) * GCD(x,y) = x * y might have come. To find LCM or GCD, one way is to break each of the numbers up into their prime factors.
Let x = 84, y = 30
x = 2*2*3*7 = (2*3)*2*7
y = 2*3*5 = (2*3)*5
The portion in bracket is the common part. So we say that ok, 2*3, i.e. 6 should be able to divide both x and y and call it the GREATEST common divisor. Mind you, only 2 or only 3 are also common divisors of x and y, but not the GREATEST common divisors.
To find the LEAST common multiple, we take the GCD and multiply it by all the numbers which are left behind. So our LCM is (2*3)*2*7*5 = 420. I'm not describing the intuition behind this as it is simple and also not relevant directly.
So if you multiply x and y, you get 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) = [common part raised to power 2, since it is repeated in both the numbers] * [the rest of the left over factors in all the numbers].
Now coming to your question, if you take one more variable z = 18 = (2*3)*3, GCD of all 3 numbers is common part (2*3), i.e., 6 and LCM is (2*3)*2*7*5*3, whatever that is.
Now x*y*z = (2*3)*(2*3)*(2*3)*(2*7*5*3) = [common part raised to power 3, since it is repeated in all 3 numbers] * [the rest of the left over factors in all the numbers]. But if you multiple GCD and LCM you will get only (2*3)*((2*3)*2*7*5*3) = (2*3)*(2*3)*(2*7*5*3), i.e. the common part is taken into consideration only twice instead of thrice.
However, it can also be the case when some of the factors between some numbers (not all, i.e. cannot be included in GCD) are common. In the general case of n variables, GDD(x[1],x[2],...x[n]) = c[1]c[2]..c[k] where each of c[i] 1<=i<=k exists once in all the numbers. LCM((x[1],x[2],...x[n]) = GCD(x[1],x[2],...x[n]) * ((h(p[1]) * h(p[2]) * ... h(p[l])) where each p[j], 1<=j<=l is a prime number in the list of left over factors not part of GCD and h(p[i]) is the highest power of p[i] present in any of them.
Now when we multiply LCM and GCD of n numbers, apart from loosing out on the factors of GCD on anything more than twice we also loose out on the factors which are partially common between some of the numbers and can only find the result of the highest powers which are present multiplied to the GCD.