Theorem1。3。2(TheEuclideanAlgorithm)假设a,b且ab。由除法原理我们知存在h0,r0使得abh0+r0，其中r0b。欧几里得算法若r00，则存在h1,r1使得br0h1+r1，其中0r1r0。若r10，则存在h2,r2使得r0r1h2+r2，其中0r2r1。
如此继续下去直到rn0为止。若n0（即r00），则gcd(a,b)b。若n1，则gcd(a,b)rn1。证明。首先注意若r00，由于r0r1r2。。。是严格递减的，因为r0和0之间最多仅能插入r01个正整数，所以我们知道一定会有nr0使得rn0。
若r00，即abh0，故知b为a之因数，得证b为a,b的最大公因数。若r00，则由Lemma1。3。1知gcd(a,b)gcd(b,r0)gcd(r0,r1）。。。gcd(rn1,rn)gcd(rn1,0)rn1。现在我们来看用辗转相除法求最大公因数的例子Example1。
3。3我们求a481和b221的最大公因数。首先由除法原理得4812。221+39，知r039。因此再考虑b221除以r039得2215。39+26，知r126。再以r039除以r126得391。26+13，知r213。最后因为r213整除r126知r30，故由Theorem1。
3。2知gcd（481,221）r213。在利用辗转相除法求最大公因数时，大家不必真的求到rn0。例如在上例中可看出r039和r126的最大公因数是13，利用Lemma1。3。1马上得知gcd(a,b)13。在上一节Corollary1。2。
5告诉我们若gcd(a,b)d，则存在m,n使得dma+nb。当时我们没有提到如何找到此m,n。我们利用辗转相除法来介绍一个找到m,n的方法。我们沿用Theorem1。3。2的符号。看r00的情形，此时dgcd(a,b)b所以若令m0,n1，则我们有dbma+nb。
当r00但r10时，我们知dgcd(a,b)r0。故利用abh0+r0知，若令m1,nh0，则dr0ma+nb。同理若r00,r10但r20，则知dgcd(a,b)r1。故利用abh0+r0以及br0h1+r1知r1br0h1b(abh0)h1h1a+（1+h0h1）b。
因此若令mh1且n1+h0h1，则dr1ma+nb。依照此法，当r0,r1和r2皆不为0时，由于dgcd(a,b)rn1故由rn3rn2hn1+rn1知drn3hn1rn2。利用前面推导方式我们知存在m1,m2,n1,n2使得rn3m1a+n1b且rn2m2a+n2b故代入欧几里得算法(2张)得d(m1a+n1b)hn1(m2a+n2b)(m1hn1m2）a+(n1hn1n2）b。
因此若令mm1hn1m2且nn1hn1n2，则dma+nb。上面的说明看似好像当r00时对每一个i{0,1,。。。,n2}要先将ri写成rimia+nib，最后才可将drn1写成ma+nb的形式。其实这只是论证时的方便，在实际操作时我们其实是将每个ri写成mi'ri2+ni'ri1的形式慢慢逆推回dma+nb。
请看以下的例子。Example1。3。4我们试着利用Example1。3。3所得结果找到m,n使得13gcd（481,221）481m+221n。首先我们有13r23926r0r1。而r12215。39b5r0，故得13r0(b5r0)6r0b。
再由r04812。221a2b，得知136(a2b)b6a13b。故得m6且n13会满足13481m+221n。要注意这里找到的m,n并不会是唯一满足dma+nb的一组解。虽然上面的推演过程好像会只有一组解，不过只能说是用上面的方法会得到一组解，并不能担保可找到所有的解。
比方说若令m'm+b,n'na，则m'a+n'b(m+b)a+(na)bma+nbd。所以m',n'也会是另一组解。所以以后当要探讨唯一性时，若没有充分的理由千万不能说由前面的推导过程看出是唯一的就断言是唯一。一般的作法是假设你有两组解，再利用这两组解所共同满足的式子找到两者之间的关系。
我们看看以下的作法。Proposition1。3。5假设a,b且dgcd(a,b)。若xm0,yn0是dax+by的一组整数解，则对任意t,xm0+bt/d,yn0at/d皆为dax+by的一组整数解，而且dax+by的所有整数解必为xm0+bt/d,yn0at/d其中t这样的形式。
证明。假设xm,yn是dax+by的一组解。由于已假设xm0,yn0也是一组解，故得am+bnam0+bn0。也就是说a(mm0)b(n0n)。由于dgcd(a,b），我们可以假设aa'd,bb'd其中a',b'且gcd(a',b')1（参见Corollary1。
2。3）。因此得a'(mm0)b'(n0n)。利用b'|a'(mm0),gcd(a',b')1以及Proposition1。2。7⑴得b'|mm0。也就是说存在t使得mm0b't。故知mm0+b'tm0+bt/d。将mm0+bt/d代回am+bnam0+bn0可得nn0at/d，因此得证dax+by的整数解都是xm0+bt/d,yn0at/d其中t这样的形式。
最后我们仅要确认对任意t,xm0+bt/d,yn0at/d皆为dax+by的一组整数解。然而将xm0+bt/d,yn0at/d代入ax+by得a(m0+bt/d)+b(n0at/d)am0+bn0d，故得证本定理。利用Proposition1。
3。5我们就可利用Example1。3。4找到13481x+221y的一组整数解x6,y13得到x6+17t,y1337t其中t是13481x+221y所有的整数解。欧几里德算法设计编辑辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：⒈若r是a÷b的余数，且r不为0，则gcd(a,b)gcd(b,r)⒉a和其倍数之最大公因子为a。
