关于欧几里得算法的原理解决方法
关于欧几里得算法的原理
在求两个整数的最大公约数要用到欧几里得算法,那么请问这欧几里得算法的原理是什么呢?
------解决方案--------------------
设A,B(A> B)最大公约数为k,则
A = k*A1
B = k*B1
所以
C = A-B*t = k*(A1-B1*t) (C <B)
得到
(A,B) == (C,B)
在求两个整数的最大公约数要用到欧几里得算法,那么请问这欧几里得算法的原理是什么呢?
------解决方案--------------------
设A,B(A> B)最大公约数为k,则
A = k*A1
B = k*B1
所以
C = A-B*t = k*(A1-B1*t) (C <B)
得到
(A,B) == (C,B)