初中奥数竞赛培优专题讲座：专题三 最大公约数与最小公倍数（PDF版）

三、最大公约数与最小公数 、最大公约数与最小公倍数 [竞赛要点] 1.最大公约数 定义1设a1,a2,…,an(n≥2)是n个整数,若整数d是这n个整数中每一个数 的约数,则称d为这n个整数的公约数 由于1是任意整数的约数,且任何非零整数的约数只有有限个,因此,我们有 定义2不全为零的n(n≥2)个整数at,a2,…,an的一切公约数中的最大数d叫 做这n个整数的最大公约数,记作(a1,a2,…,an),即(a1,a2,…,an)=d 特别地,若(a1,a2,…,an)=1,则称整数a1,a2,…,an互质.若a1,a2,…,an中任 意两个整数都互质,则称a1,a2,…,an两两互质 初 显然,若a1,a2,…,an两两互质,则这n个数必互质,反之则不真例如,(6,10,|数 15)=1,但(6,10)=2,(10,15)=5,(15,6)=3 学 竞 2.最小公倍数 赛 定义3设a1,a,…,an(mn≥2)是n个非零整数,若m是这n个数中每一个a 的倍数,则称m为这n个数的一个公倍数,其所有正的公倍数中最小的一个叫做这n教 个整数的最小公倍数,记作[a1,a2,…,an] 程 专 型 [方法述要] 题 讲 定理1设a,b是两个正整数,则a,b的最大公约数(a,b)=rn,其中a=的+/座 r1,(0<r<|1),b=r1q2+r2(0<r2<r1),r1=r2q3+r3(0<r3<r2), -19n+r (0<r<r-1). 定理2不同为零的整数a,b的任意公约数是它们的最大公约数(a,b)的约数 定理3设a,b是不同为零的整数,则对任意整数k有(a,b)=(a,b+ka 定理4设a,b是不同为零的整数,则对任意正整数k有(ka,kb)=k(a,b) 定理5设(a,b)=1,则对任意整数k,有(ka,b)=(k,b) 定理6设c是a,b的正公约数,则(,0)= b 定理7若a,b是不同为零的整数,则存在整数x,y,使ax+by=(a,b) 定理8设a1,a2,…,an是n个正整数,且(a1,a2)=d2,(d2,a3)=d3,…, 三、最大公约数与最小公修数 an)=dn,则(a1,a2 定理9设a1,a2,…,an为n个不全为零的整数(n≥2),则(a1,a2,…,an)= [(a1,a2, 定理10设 an为n(n≥2)个不全为零的整数,则存在n个整数x1