两个正整数的最大公约数的辗转相除法
设a、b是正整数，且a＞b．为求a，b的最大公约数，首先以b除a，得：a＝q 1 b＋r 1 ，式中q 1 和r 1 为非负整数，0≤r 1 ＜b．若r 1 ＝0，则a＝q 1 b，a和b的最大公约数（a，b）＝b；若r 1 ≠0，则0＜r 1 ＜b，以r 1 除b，得：b＝q 2 r 1 ＋r 2 ，式中q 2 和r 2 为非负整数，0≤r 2 ＜r 1 ．若r 2 ＝0，则b＝q 2 r 1 ，b和r 1 的最大公约数（b，r 1 ）＝r 1 ；若r 2 ≠0，则0＜r 2 ＜r 1 ，以r 2 除r 1 且得：r 1 ＝q 3 r 2 ＋r 3 ，式中q 3 和r 3 为非负整数，0≤r 3 ＜r 2 ．
若r 3 ＝0，则（r 1 ，r 2 ）＝r 2 ．从式a＝q 1 b＋r 1 ，b＝q 2 r 1 ＋r 2 和r 1 ＝q 3 r 2 ＋r 3 及“若整数d可整除三个等式每个等式中的某两项，则必可整除其第三项”知（a，b）＝（b，r 1 ）＝（r 1 ，r 2 ）．若0＜r 3 ＜r 2 ，则再以r 3 除r 2 ，并继续上述讨论，……，一直辗转相除下去。
由于b＞r 1 ＞r 2 ＞r 3 ＞…和所有r i （i＝1，2，3，…）都是非负整数，所以必存在正整数n，使得经过n＋1次辗转相除后有r n＋1 ＝0，而r n ≠0．于是（a，b）＝（b，r 1 ）＝（r 1 ，r 2 ）＝…＝（r n－1 ，r n ）＝r n ．显然，由定理4.1.1，运用辗转相除法可求任意两个整数的最大公约数。
【例1-1】
求6731和2809的最大公约数。
解：由6731＝2×2809＋1113，2809＝2×1113＋583，1113＝1×583＋530，583＝1×530＋53，530＝10×53＋0知（6731，2809）＝53。
