如何求最大公因子？

定义11.4 对于整数a、b、c，如果c|a，c|b，则称c为a和b的公因子（或公约数）。其中最大的公因子称为最大公因子（或最大公约数）。a和b的最大公因子d满足以下条件：d＞0，d|a，d|b，且对a和b的任意公因子c，有c|d。一般记a和b的最大公因子为gcd（a，b）或者简记为（a，b）。

显然，对于最大公因子有下面的结果：

1）对任意的整数a和b，gcd（a，0）=|a|，gcd（a，b）=gcd（|a|，|b|）。因此，在设计求两个整数的最大公因子的算法时只需要考虑正整数。

2）对任意的正整数m，有gcd（am，bm）=gcd（a，b）m。

3）设h|a，h|b且h＞0，则gcd（a/h，b/h）=gcd（a，b）/h。

4）若a和b是两个不全为0的整数，则存在整数s和t，使得as+bt=gcd（a，b）。

定义11.5 如果两个整数a和b的最大公因子为1，即gcd（a，b）=1，则称这两个整数互素。互素具有以下基本性质：

1）如果gcd（a，b）=1，gcd（a，c）=1，则gcd（a，bc）=1。

2）如果gcd（a，b）=1，且a|bc，则a|c。

3）如果gcd（a，b）=1，且a|c，b|c，则ab|c。

4）如果gcd（a，b）=1，则存在整数s和t，使得as+bt=1。

另外，关于最大公因子还有下面的定理。

定理11.8 如果a=bq+r，b≠0且a、b、q、r为整数，则

gcd（a，b）=gcd（b，r）。

根据表达式a=bq+r可知，如果d是a与b的公因子，则d|a，d|b，故d|（a-bq），d|r，所以d也是b和r的公因子，即a与b，b与r的公因子相同。

这个定理给出了求最大公因子的方法，称为辗转相除法，也称为欧几里得（Euclid）算法。其具体思想描述如下：

设a与b是两个非零的整数，且b不整除a，则根据带余除法定理可以写出一串等式

由于余数r₁＞r₂＞…＞r_i＞…，即每进行一次带余除法，余数至少要减1，而|b|是一个有限的正整数，有限步后，这一计算过程必然要终止，因而我们总可以得到一个余数是零的等式，即r_n+1=0。根据以上定理可知，gcd（a，b）=gcd（b，r₁）=gcd（r₁，r₂）=…=gcd（r_n，r_n+1）=r_n。

应用模运算可以将定理11.8表述为另一种形式：对任意的整数a和b，有

gcd（a，b）=gcd（b，a（mod b））

根据前面的分析，只要重复地执行上式直到后面的一项为0，前面的数即为这两个数的最大公因子。此思想可用以下欧几里得算法描述为：(www.xing528.com)

EUCLID（a，b且满足a＞b＞0）

1）X←a；Y←b；

2）如果Y=0，则输出X=gcd（a，b）；

3）R←X（mod Y）；

4）X←Y；

5）Y←R；

6）转到2）。

此算法中只涉及正整数，最大公因子与整数的符号没有关系。

【例11-16】 设a=3371，b=1435，计算gcd（a，b）。

【解析】 由于 3371=2×1435+501

1435=2×501+433

501=433+68

433=6×68+25

68=2×25+18

25=18+7

18=2×7+4

7=4+3

4=3+1

3=3×1

所以gcd（3371，1435）=1