辗转相除法根据辗转相除法第一步输入两个正整数MN第二步计算M除以N所得的余数R第三步M=NN=R第四步若R=0则MN的最大公约数等于N否则转到第二步若设M/N=A1.R1R1不等于0M=NN=R1N/R1=A2.R2R2

　　辗转相除法

　　根据辗转相除法第一步输入两个正整数MN

　　第二步计算M除以N所得的余数R

　　第三步M=NN=R

　　第四步若R=0则MN的最大公约数等于N否则转到第二步

　　若设M/N=A1.R1R1不等于0M=NN=R1

　　N/R1=A2.R2R2不等于0N=R1R1=R2

　　R1/R2=A3.R3.

　　以此类推求M的通项公式