早教吧 育儿知识 作业答案 考试题库 百科 知识分享

辗转相除法的推倒过程或者说gcd(a,b)=gcd(b,amodb)gcd(a,b)=gcd(b,a-b)gcd(a,b)*lcm(a,b)=ab这个两个公式的推倒过程

题目详情
辗转相除法的推倒过程
或者说 gcd(a,b)=gcd(b,a mod b)
gcd(a,b)=gcd(b,a-b)
gcd(a,b) * lcm(a,b) = ab
这个两个公式的推倒过程
▼优质解答
答案和解析
设两数为a、b(b<a),求它们最大公约数(a、b)的步骤如下:用b除a,得a=bq?1+r?1(0≤r?1<b).若r?1=0,则(a,b)=b;若r?1≠0,则再用r?1除b,得b=r?1q?2+r?2(0≤r?2<r?1).若r?2=0,则(a,b)=r?1,若r?2≠0,则继续...