6．欧几里得辗转相除法
大家熟悉一个整数a被另一个整数b去长除，如果在余数小于除数之前，这个步骤能一直进行下去，如，a＝648，b＝7。我们得到商q＝92，余数r＝4，则648＝92·7＋4。我们可以把这个过程叙述为一个定理：如果a是任意一整数，b是任意一大于0的整数，则我们总能找到一个整数q，使a＝b·q＋r，其中0＜＝r＜b是－个整数
下面我们用这－定理来求两个整数的最大公因子，记d＝(a、b)表示最大公因子，这就是辗转相除法：对于任意两整数a、b，若a＝bq＋r (b＝／0)，则(a、b)＝(b、r)。这是因为对任意同时整除a和b的数u，有a＝su，b＝tu，那么r＝a－bq＝su－tuq＝(s－tq)u也能被u整除，反过来，每个整除b和r的整数v，有b＝s’v，r＝t’v，它也整除a，这是因为a＝(s’q＋t’)v，因此a和b的公因子集和b与r的公因子集相同。这就证明了上面所述定理。
例．求1804和328的最大公因子
首先按照普通除法得1804＝5·328＋164；第二步继续第一步得328＝2·164＋0；
所以d＝(328、164)＝(164、0)＝164
