greatest-common-divisor - 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

括号中的部分为通用部分。所以我们说好的，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。