离散数学：最大公因数和最小公倍数

公因数、最大公因数：设a1，a2，…，an和d都是正整数，n≥2.若d|ai（1≤i≤n），则称d是a1，a2，…，an的公因数.所有公因数中最大的那一个数，称为a1，a2，…，an的最大公因数，记为（a1，a2，…，an）.若（a1，a2，…，an）=1，则称a1，a2，…，an是互素的.

定理6.8　在定理6.7的条件和符号下，有（u0，u1）=（u1，u2）=…=（uk-1，uk）=（uk，uk+1）=uk+1.

定理6.9　对任意给定的正整数a和b，则存在整数x和y，使得（a，b）=ax+by.

定理6.10　公因数一定是最大公因数的因数.

定理6.11　对任意给定的正整数a和b，若（a，b）=d，则（a/d，b/d）=1.

公倍数、最小公倍数：设a1，a2，…，an和m都是正整数，n≥2.若ai|m（1≤i≤n），则称m是a1，a2，…，an的公倍数.所有公倍数中最小的那一个数，称为a1，a2，…，an的最小公倍数，记为［a1，a2，…，an］.(www.xing528.com)

定理6.12　给定正整数a和b，且［a，b］=m，若m′是a和b的公倍数，则m|m′.

定理6.13　设a和b是正整数，且（a，b）=d，［a，b］=m，则ab=dm.

定理6.14　设a，b，c都是正整数，若a|bc，且（a，b）=1，则a|c.

定理6.15　设a，b，c都是正整数，且（a，b）=1，c|a，则（b，c）=1.

定理6.16　设a，b，c都是正整数，若a|c，b|c，且（a，b）=1，则ab|c.