更相减损法 为什么可以用于求最大公约数呢?即它的原理是什么?
问题描述：
更相减损法 为什么可以用于求最大公约数呢?即它的原理是什么?
答
更相减损术是中国古人用的机械化算法。
对所求两数，其公约数同样能约他们的差。
答
我认为更相减损法的原理就是同余啊.
两数X = AP,Y = BP
P是最大公约数,A>B且互素,则BP、（A-B）P同样必有最大公约数P,
更相减损,最后必求得1P.