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的公因數，反之亦然。這樣，由於A和B的所有公因式集合都與B和R的公因式集合相同，所以A和B的最大公因式壹定等於B和R的最大公因式。
其實還有壹個更減法的技巧，也是求最大公約數的好方法。