如何证明gcd(a,b,c)=gcd(gcd(a,b),c)

如何证明gcd(a,b,c)=gcd(gcd(a,b),c)
如何证明gcd(a,b,c)=gcd(gcd(a,b),c)

如何证明gcd(a,b,c)=gcd(gcd(a,b),c)
gcd(a,b,c)是a,b,c的公约数,故gcd(a,b,c)能分别整除a,b,c,由gcd(a,b,c)能整除a,b,且gcd(a,b)是a,b的最大公约数,于是gcd(a,b,c)能整除gcd(a,b),并能整除c,故gcd(a,b,c)是gcd(a,b)和c的公约数,gcd(gcd(a,b),c)是gcd(a,b)和c的最大公约数.故gcd(a,b,c)能整除gcd(gcd(a,b),c).
gcd(gcd(a,b),c)是gcd(a,b),c的公约数,故gcd(gcd(a,b),c)能整除gcd(a,b),并能整除c,于是gcd(gcd(a,b),c)能整除a,b和c,gcd(a,b,c)是a,b,c的最大公约数,故gcd(gcd(a,b),c)能整除gcd(a,b,c).
由gcd(a,b,c)能整除gcd(gcd(a,b),c),gcd(gcd(a,b),c)能整除gcd(a,b,c).故得gcd(a,b,c)=gcd(gcd(a,b),c).

首先证明引理1:
若k是a,b的公因子,m是a,b的最大公因子
则k必整除m
证明过程:
将a,b分解为素数之积:
a=a1*a2*a3...*an*c1*c2*c3...*cn
b=b1*b2*b3...*bm*c1*c2*c3...*cn
其中c1到cn表示a,b中相同的因子
那么m=c1*c2*c3...*cn
而k是c...

全部展开

首先证明引理1:
若k是a,b的公因子,m是a,b的最大公因子
则k必整除m
证明过程:
将a,b分解为素数之积:
a=a1*a2*a3...*an*c1*c2*c3...*cn
b=b1*b2*b3...*bm*c1*c2*c3...*cn
其中c1到cn表示a,b中相同的因子
那么m=c1*c2*c3...*cn
而k是c1到cn中任意个的乘积,所以m能整除k
引理1证毕
所以
a,b,c的公因子必是 gcd(a,b)和c的公因子 (1)
很简单,若k能整除a,b,c
那么k必能整除 gcd(a,b)--根据引理1,同时也能整除c. 同理
gcd(a,b)和c的公因子也是a,b,c的公因子 (2)--这个就更简单了,若能整除gcd(a,b)那肯定能整除a和b
由(1)和(2) 可得a,b,c的最大公因子和gcd(a,b),c的最大公因子必须相等, 否则其中小的一个就不是最大公因子(因为还能找到比它更大的)

收起

任何正整数 n 均可唯一地写成如下形式：
n = p1^e1 * p2^e2 * p3^e3 * ...
其中 p1, p2, p3, .. 是所有的素数，即 p1 = 2, p2 = 3, p3 = 5, ...，e1, e2, e3, ... 是他们的幂。
例如：
30 = 2^1 * 3^1 * 5^1 * 7^0 * 11^0 * ...
13 = ...

全部展开

任何正整数 n 均可唯一地写成如下形式：
n = p1^e1 * p2^e2 * p3^e3 * ...
其中 p1, p2, p3, .. 是所有的素数，即 p1 = 2, p2 = 3, p3 = 5, ...，e1, e2, e3, ... 是他们的幂。
例如：
30 = 2^1 * 3^1 * 5^1 * 7^0 * 11^0 * ...
13 = 2^0 * 3^0 * 5^0 * 7^0 * 11^0 * 13^1 * 17^0 * ...
8 = 2^3 * 3^0 * 5^0 * ...
两个整数 a, b 的最大公约数 gcd(a,b)，它应该包含两数共有的所有素因子，也就是说，假如 a，b 分别分解如下：
a = p1^a1 * p2^a2 * p3^a3 * ...
b = p1^b1 * p2^b2 * p3^b3 * ...
那么对于每个素因子，比如 p1，既然 a 包含 a1 个 p1，b 包含 b1 个 p1，那么他们的最大公约数就只能包含 min(a1, b1) 个 p1。于是就有：
gcd(a,b) = p1^min(a1,b1) * p2^min(a2,b2) * p3^min(a3,b3) * ...
（min(x,y) 表示取 x,y 的较小值。）
比如对于 8 和 12：
8 = 2^3 * 3^0 * 5^0 * ...
12 = 2^2 * 3^1 * 5^0 * ...
于是就有：
gcd(8, 12) = 2^min(3,2) * 3^min(0,1) * 5^min(0,0) * ... = 2^2 * 3^0 * 5^0 = 4
顺便说一句，最小公倍数 lcm(a,b) 其实就是：
lcm(a,b) = p1^max(a1,b1) * p2^max(a2,b2) * p3^max(a3,b3) * ...
（max(x,y) 表示取 x,y 的较大值。）
由上面这点也不难看出有 lcm(a,b)*gcd(a,b) = a*b;
现在来证明楼主的问题：
gcd(a,b,c) 如果对 a,b,c 分别分
a = p1^a1 * p2^a2 * p3^a3 * ...
b = p1^b1 * p2^b2 * p3^b3 * ...
c = p1^c1 * p2^c2 * p3^c3 * ...
那么最大公约数就是：
gcd(a,b,c) = p1^min(a1,b1,c1) * p2^min(a2,b2,c2) * p3^min(a3,b3,c3) * ...
显然 min(x,y,z) = min(min(x, y), z)
所以 gcd(a,b,c) 也等于：
gcd(a,b,c) = p1^min(min(a1,b1),c1) * p2^min(min(a2,b2),c2) * p3^min(min(a3,b3),c3) * ... = gcd(gcd(a,b),c)

收起