最大公约数与最小公倍数解决方法

分类: IT文章 • 2023-12-22 13:44:13

最大公约数与最小公倍数
两数的最小公倍数等于两数之积除以最大公倍数。
为何？
------解决方案--------------------
考虑素数p,分解a后有p的u次方,b中有p的v次方.
于是最大公约数中p的指数是min(u, v),最小公倍数中p的指数是max(u, v),乘积中p的指数是u+v
u+v-min(u, v) = max(u, v)
对所有的素数都有上式,于是有结果.