最大公约数和最小公倍数
2026-03-21 16:55:20
发布于：上海
证明如何为何辗转相除法能够做最大公约数和最小公倍数的一篇。
最大公约数：(a>b)
公式是gcd(a,b)=gcd((min(a,b),a%b);
如何证明：（从百度百科学和豆包那里学的）
a可以表示成：a=kb+r
假设d是a,b的公约数：a=ud,b=vd。
则r=a-kb=ud-kb=ud-kvd=(u-kv)d。
那么d也是b，r的公约数。
a,b,r有相同的公约数。
同理，设e是b,r的一个公约数。
记b=xe,r=ye,则a=kb+r=kxe+ye=(kx+y)e
所以e也是a的因子。
取d=gcd(a,b) ，e=gcd(b,r) 。（注意，这里的d和e可以是任何公约数，但是取成了最大公约数。）
因为：一组数的最大公约数是这组所有公约数的倍数。
d是b,r的公约数，e是b,r的最大公约数。
所以：d是e的因子。设e=pd。
而：
e是a,b的公约数，d是a,b的最大公约数。
所以：e是d的因子。设d=ve。
推一下：d=ve=vpd
所以：vp=1
因为v>0且p>0。
所以：v=1,p=1。
所以：e=d。
所以：gcd(a,b)=gcd(b,r)
即：gcd(a,b)=gcd(min(b,a) , a%b))
最小公倍数：
最小公倍数就比最大公约数要简单一些了。
lcm(a,b)=a* b/gcd(a,b)。
如何证明？（学习自洛谷yurzhang）
假设gcd(a,b)=d，那么可以设a=d* u，b=d* v。这样gcd(u,v)=1。
因此lcm(a,b)=lcm(d* u,d* v)=dlcm(u,v)=d u* v
因此gcd(a,b)*lcm(a,b)=d * d * u * v=a * b
例题：链接描述
byebye.
如果 有 不理解的 地方 可以 尝试 发在评论区里 虽然 我 不一定 会 解答 但是 可能 会有 好心人 愿意 解答
再见
我还会回来的
这里空空如也
有帮助，赞一个