数论题，最大公因子与最小公倍数证明

1个回答

小钰学姐oO

专业答主服务有保障

关注

展开全部

摘要最大公因数，也即最大公约数。最大公约数即为 Greatest Common Divisor，常缩写为 gcd。我们求出最大公因数可以用于分数的约分问题，只要分子、分母都除以最大公因数d。最常用的求最大公因数的方法时欧几里得算法，也即辗转相除法。时间复杂度为O(logn)O(logn)。欧几里得算法基于下面的定理：设a，b为均正整数，则gcd(a,b) = gcd(b,a%b)。

咨询记录 · 回答于2022-12-24

数论题，最大公因子与最小公倍数证明

最大公因数，也即最大公约数。最大公约数即为 Greatest Common Divisor，常缩写为 gcd。我们求出最大公因数可以用于分数的约分问题，只要分子、分母都除以最大公因数d。最常用的求最大公因数的方法时欧几里得算法，也即辗转相除法。时间复杂度为O(logn)O(logn)。欧几里得算法基于下面的定理：设a，b为均正整数，则gcd(a,b) = gcd(b,a%b)。

第二题怎么做

这不是这题的答案吧？题干都不对

(a,[b,c])=(a,bc/(b,c) )=(a,bc)/(a,(b,c))=(a,b)*(a,c)/(a,b,c)=(a,b)*(a,c)/((a,b),(a,c))=[(a,b),(a,c)]

可以再详细一点嘛？看不太懂

这个就是详细的过程了呀

但你打的字我看不明白，加减乘除号是乱的

(a,[b,c])=(a,bc/(b,c) )=(a,bc)/(a,(b,c))=(a,b)*(a,c)/(a,b,c)=(a,b)*(a,c)/((a,b),(a,c))=[(a,b),(a,c)]

已赞过

评论收起