最大公因数与最小公倍数的关系（公式推导）
最大公因数与最小公倍数公式概览
a
,
b
a,b
a,b 的最小公倍数
l
c
m
(
a
,
b
)
lcm(a,b)
lcm(a,b)
a
,
b
a,b
a,b 的最大公因数
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b)
a
,
b
,
c
a,b,c
a,b,c 的最小公倍数
l
c
m
(
l
c
m
(
a
,
b
)
,
c
)
lcm(lcm(a,b),c)
lcm(lcm(a,b),c) （二者先求最小公倍数，结果与第三个数求最小公倍数）
a
,
b
,
c
a,b,c
a,b,c 的最大公因数
g
c
d
(
g
c
d
(
a
,
b
)
,
c
)
gcd(gcd(a,b),c)
gcd(gcd(a,b),c) （二者先求最大公因数，结果与第三个数求最大公因数）
l
c
m
(
a
,
b
)
=
a
×
b
/
g
c
d
(
a
,
b
)
lcm(a,b)=a\times b /gcd(a,b)
lcm(a,b)=a×b/gcd(a,b)
g
c
d
(
l
c
m
(
a
,
b
)
,
c
)
=
l
c
m
(
g
c
d
(
a
,
c
)
,
g
c
d
(
b
,
c
)
)
gcd(lcm(a,b),c)=lcm(gcd(a,c),gcd(b,c))
gcd(lcm(a,b),c)=lcm(gcd(a,c),gcd(b,c))
g
c
d
(
l
c
m
(
a
,
b
)
,
c
)
=
l
c
m
(
g
c
d
(
a
,
c
)
,
g
c
d
(
b
,
c
)
)
gcd(lcm(a,b),c)=lcm(gcd(a,c),gcd(b,c))
gcd(lcm(a,b),c)=lcm(gcd(a,c),gcd(b,c))推导
初步理解
首先，我需要理解
gcd
\text{gcd}
gcd 和
lcm
\text{lcm}
lcm 的定义及其基本性质。
最大公因数（
gcd
\text{gcd}
gcd）：两个或多个整数共有约数中最大的一个。最小公倍数（
lcm
\text{lcm}
lcm）：两个或多个整数共有倍数中最小的一个。
此外，
gcd
\text{gcd}
gcd 和
lcm
\text{lcm}
lcm 之间有一个重要的关系：
gcd
(
a
,
b
)
×
lcm
(
a
,
b
)
=
a
×
b
\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b
gcd(a,b)×lcm(a,b)=a×b
分析等式
我们需要证明的等式涉及三个变量
a
a
a,
b
b
b,
c
c
c，并且结合了
gcd
\text{gcd}
gcd 和
lcm
\text{lcm}
lcm 的运算。为了简化问题，我考虑使用素因数分解的方法，因为
gcd
\text{gcd}
gcd 和
lcm
\text{lcm}
lcm 都可以通过素因数分解来表示。
素因数分解法
假设
a
a
a,
b
b
b,
c
c
c 的素因数分解分别为：
a
=
∏
p
p
α
p
,
b
=
∏
p
p
β
p
,
c
=
∏
p
p
γ
p
a = \prod_{p} p^{\alpha_p}, \quad b = \prod_{p} p^{\beta_p}, \quad c = \prod_{p} p^{\gamma_p}
a=p∏pαp,b=p∏pβp,c=p∏pγp
其中，
p
p
p 是素数，
α
p
\alpha_p
αp,
β
p
\beta_p
βp,
γ
p
\gamma_p
γp 是非负整数，表示对应素数的幂次。
根据素因数分解，
gcd
\text{gcd}
gcd 和
lcm
\text{lcm}
lcm 可以表示为：
gcd
(
a
,
b
)
=
∏
p
p
min
(
α
p
,
β
p
)
\text{gcd}(a, b) = \prod_{p} p^{\min(\alpha_p, \beta_p)}
gcd(a,b)=p∏pmin(αp,βp)
lcm
(
a
,
b
)
=
∏
p
p
max
(
α
p
,
β
p
)
\text{lcm}(a, b) = \prod_{p} p^{\max(\alpha_p, \beta_p)}
lcm(a,b)=p∏pmax(αp,βp)
表达式的素因数分解
现在，我们将等式两边的表达式用素因数分解表示。
左边：
gcd
(
lcm
(
a
,
b
)
,
c
)
\text{gcd}(\text{lcm}(a, b), c)
gcd(lcm(a,b),c)
首先，计算
lcm
(
a
,
b
)
\text{lcm}(a, b)
lcm(a,b)：
lcm
(
a
,
b
)
=
∏
p
p
max
(
α
p
,
β
p
)
\text{lcm}(a, b) = \prod_{p} p^{\max(\alpha_p, \beta_p)}
lcm(a,b)=p∏pmax(αp,βp)
然后，计算
gcd
(
lcm
(
a
,
b
)
,
c
)
\text{gcd}(\text{lcm}(a, b), c)
gcd(lcm(a,b),c)：
gcd
(
lcm
(
a
,
b
)
,
c
)
=
∏
p
p
min
(
max
(
α
p
,
β
p
)
,
γ
p
)
\text{gcd}(\text{lcm}(a, b), c) = \prod_{p} p^{\min(\max(\alpha_p, \beta_p), \gamma_p)}
gcd(lcm(a,b),c)=p∏pmin(max(αp,βp),γp)
右边：
lcm
(
gcd
(
a
,
c
)
,
gcd
(
b
,
c
)
)
\text{lcm}(\text{gcd}(a, c), \text{gcd}(b, c))
lcm(gcd(a,c),gcd(b,c))
首先，计算
gcd
(
a
,
c
)
\text{gcd}(a, c)
gcd(a,c) 和
gcd
(
b
,
c
)
\text{gcd}(b, c)
gcd(b,c)：
gcd
(
a
,
c
)
=
∏
p
p
min
(
α
p
,
γ
p
)
\text{gcd}(a, c) = \prod_{p} p^{\min(\alpha_p, \gamma_p)}
gcd(a,c)=p∏pmin(αp,γp)
gcd
(
b
,
c
)
=
∏
p
p
min
(
β
p
,
γ
p
)
\text{gcd}(b, c) = \prod_{p} p^{\min(\beta_p, \gamma_p)}
gcd(b,c)=p∏pmin(βp,γp)
然后，计算
lcm
(
gcd
(
a
,
c
)
,
gcd
(
b
,
c
)
)
\text{lcm}(\text{gcd}(a, c), \text{gcd}(b, c))
lcm(gcd(a,c),gcd(b,c))：
lcm
(
gcd
(
a
,
c
)
,
gcd
(
b
,
c
)
)
=
∏
p
p
max
(
min
(
α
p
,
γ
p
)
,
min
(
β
p
,
γ
p
)
)
\text{lcm}(\text{gcd}(a, c), \text{gcd}(b, c)) = \prod_{p} p^{\max(\min(\alpha_p, \gamma_p), \min(\beta_p, \gamma_p))}
lcm(gcd(a,c),gcd(b,c))=p∏pmax(min(αp,γp),min(βp,γp))
比较两边的素因数分解
现在，我们需要证明：
∏
p
p
min
(
max
(
α
p
,
β
p
)
,
γ
p
)
=
∏
p
p
max
(
min
(
α
p
,
γ
p
)
,
min
(
β
p
,
γ
p
)
)
\prod_{p} p^{\min(\max(\alpha_p, \beta_p), \gamma_p)} = \prod_{p} p^{\max(\min(\alpha_p, \gamma_p), \min(\beta_p, \gamma_p))}
p∏pmin(max(αp,βp),γp)=p∏pmax(min(αp,γp),min(βp,γp))
由于素因数分解的唯一性，我们只需要证明对于每一个素数
p
p
p，指数部分相等即可：
min
(
max
(
α
p
,
β
p
)
,
γ
p
)
=
max
(
min
(
α
p
,
γ
p
)
,
min
(
β
p
,
γ
p
)
)
\min(\max(\alpha_p, \beta_p), \gamma_p) = \max(\min(\alpha_p, \gamma_p), \min(\beta_p, \gamma_p))
min(max(αp,βp),γp)=max(min(αp,γp),min(βp,γp))
证明指数部分相等
我们需要证明：
min
(
max
(
α
p
,
β
p
)
,
γ
p
)
=
max
(
min
(
α
p
,
γ
p
)
,
min
(
β
p
,
γ
p
)
)
\min(\max(\alpha_p, \beta_p), \gamma_p) = \max(\min(\alpha_p, \gamma_p), \min(\beta_p, \gamma_p))
min(max(αp,βp),γp)=max(min(αp,γp),min(βp,γp))
为了简化符号，设：
x
=
α
p
,
y
=
β
p
,
z
=
γ
p
x = \alpha_p, \quad y = \beta_p, \quad z = \gamma_p
x=αp,y=βp,z=γp
则我们需要证明：
min
(
max
(
x
,
y
)
,
z
)
=
max
(
min
(
x
,
z
)
,
min
(
y
,
z
)
)
\min(\max(x, y), z) = \max(\min(x, z), \min(y, z))
min(max(x,y),z)=max(min(x,z),min(y,z))
分析不同情况
为了证明上述等式，我们可以考虑
x
x
x,
y
y
y,
z
z
z 之间的大小关系。由于
max
\max
max 和
min
\min
min 函数的对称性，我们可以假设
x
≤
y
x \leq y
x≤y 而不失一般性。因此，我们有以下几种情况：
情况一：
z
≤
x
≤
y
z \leq x \leq y
z≤x≤y情况二：
x
≤
z
≤
y
x \leq z \leq y
x≤z≤y情况三：
x
≤
y
≤
z
x \leq y \leq z
x≤y≤z
我们逐一分析这些情况。
情况一：
z
≤
x
≤
y
z \leq x \leq y
z≤x≤y
max
(
x
,
y
)
=
y
\max(x, y) = y
max(x,y)=y
min
(
max
(
x
,
y
)
,
z
)
=
min
(
y
,
z
)
=
z
\min(\max(x, y), z) = \min(y, z) = z
min(max(x,y),z)=min(y,z)=z （因为
z
≤
y
z \leq y
z≤y）
min
(
x
,
z
)
=
z
\min(x, z) = z
min(x,z)=z （因为
z
≤
x
z \leq x
z≤x）
min
(
y
,
z
)
=
z
\min(y, z) = z
min(y,z)=z （因为
z
≤
y
z \leq y
z≤y）
max
(
min
(
x
,
z
)
,
min
(
y
,
z
)
)
=
max
(
z
,
z
)
=
z
\max(\min(x, z), \min(y, z)) = \max(z, z) = z
max(min(x,z),min(y,z))=max(z,z)=z
因此，两边相等。
情况二：
x
≤
z
≤
y
x \leq z \leq y
x≤z≤y
max
(
x
,
y
)
=
y
\max(x, y) = y
max(x,y)=y
min
(
max
(
x
,
y
)
,
z
)
=
min
(
y
,
z
)
=
z
\min(\max(x, y), z) = \min(y, z) = z
min(max(x,y),z)=min(y,z)=z （因为
z
≤
y
z \leq y
z≤y）
min
(
x
,
z
)
=
x
\min(x, z) = x
min(x,z)=x （因为
x
≤
z
x \leq z
x≤z）
min
(
y
,
z
)
=
z
\min(y, z) = z
min(y,z)=z （因为
z
≤
y
z \leq y
z≤y）
max
(
min
(
x
,
z
)
,
min
(
y
,
z
)
)
=
max
(
x
,
z
)
=
z
\max(\min(x, z), \min(y, z)) = \max(x, z) = z
max(min(x,z),min(y,z))=max(x,z)=z
因此，两边相等。
情况三：
x
≤
y
≤
z
x \leq y \leq z
x≤y≤z
max
(
x
,
y
)
=
y
\max(x, y) = y
max(x,y)=y
min
(
max
(
x
,
y
)
,
z
)
=
min
(
y
,
z
)
=
y
\min(\max(x, y), z) = \min(y, z) = y
min(max(x,y),z)=min(y,z)=y （因为
y
≤
z
y \leq z
y≤z）
min
(
x
,
z
)
=
x
\min(x, z) = x
min(x,z)=x （因为
x
≤
z
x \leq z
x≤z）
min
(
y
,
z
)
=
y
\min(y, z) = y
min(y,z)=y （因为
y
≤
z
y \leq z
y≤z）
max
(
min
(
x
,
z
)
,
min
(
y
,
z
)
)
=
max
(
x
,
y
)
=
y
\max(\min(x, z), \min(y, z)) = \max(x, y) = y
max(min(x,z),min(y,z))=max(x,y)=y
因此，两边相等。
结论
通过以上三种情况的分析，我们发现对于任意非负整数
x
x
x,
y
y
y,
z
z
z，都有：
min
(
max
(
x
,
y
)
,
z
)
=
max
(
min
(
x
,
z
)
,
min
(
y
,
z
)
)
\min(\max(x, y), z) = \max(\min(x, z), \min(y, z))
min(max(x,y),z)=max(min(x,z),min(y,z))
因此，原等式成立：
gcd
(
lcm
(
a
,
b
)
,
c
)
=
lcm
(
gcd
(
a
,
c
)
,
gcd
(
b
,
c
)
)
\text{gcd}(\text{lcm}(a, b), c) = \text{lcm}(\text{gcd}(a, c), \text{gcd}(b, c))
gcd(lcm(a,b),c)=lcm(gcd(a,c),gcd(b,c))
最终答案
通过素因数分解和分情况讨论，我们证明了：
gcd
(
lcm
(
a
,
b
)
,
c
)
=
lcm
(
gcd
(
a
,
c
)
,
gcd
(
b
,
c
)
)
\text{gcd}(\text{lcm}(a, b), c) = \text{lcm}(\text{gcd}(a, c), \text{gcd}(b, c))
gcd(lcm(a,b),c)=lcm(gcd(a,c),gcd(b,c))
爆爽的双低音喇叭！甲盾Z105音箱评测
给大厂的面试难度排了个序（根据最新数据）