求两个数的最大公约数为什么可用辗转相除法,原理是什么
问题描述：
求两个数的最大公约数为什么可用辗转相除法,原理是什么
答
因为对任意同时整除a和b的数u,有a=su,b=tu,它也能整除r,因为r=a-bq=su-qtu=(s-qt)u.反过来每一个整除b和r的整数v,有b=s'v ,r=t'v它也能整除a,因为a=bq+r=s'vq+t'v=(s'q+t')v.因此a和b的每一个公因子同时也是b和r的一...