欧几里德算法原理编辑Lemma1.3.1若a,b且abh+r，其中h,r，则gcd(a,b)gcd(b,r).证明.假设d1gcd(a,b)且d2gcd(b,r).我们证明d1|d2且d2|d1，因而可利用Proposition1.1.3⑵以及d1,d2皆为正数得证d1d2.因d1|a且d1|b利用Corollary1.1.2我们知d1|abhr.因为d1|b,d1|r且d2gcd(b,r)故由Proposition1.2.5知d1|d2.另一方面，因为d2|b且d2|r故d2|bh+ra.因此可得d2|d1.Lemma1.3.1告诉我们当ab0时，要求a,b的最大公因数我们可以先将a除以b所得余数若为r，则a,b的最大公因数等于b和r的最大公因数.因为rba，所以当然把计算简化了.接着我们就来看看辗转相除法.由于gcd(a,b)gcd(a,b)所以我们只要考虑a,b都是正整数的情况
