最大公约数,也称
最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、
辗转相除法、更相减损法。
质因数分解法:就是把一个合数分解成几个
质数相乘的形式。
48和54
48=2*2*2*2*3
54=2*3*3*3
因此,48和54的最大公约数是:2*3=6.
短除法是求最大公因数的一种方法,也可用来求最小公倍数。求几个数最大公因数的方法,开始时用观察比较的方法,即:先把每个数的因数找出来,然后再找出公因数,最后在公因数中找出最大公因数.
辗转相除法是用来求最大公约数的.给出两个
正整数a和b,用b除a得商a0,余数r,写成式子 a=a0b+r,0≤r<b.
(1) 这是最基本的式子,辗转相除法的灵魂.如果r等于0,那么b可以除尽a,而a、b的最大公约数就是b. 如果r≠0,再用r除b,得商a1,余数r1,即 b=a1r+r1,0≤r1<r.
(2) 如果r1=0,那么r除尽b,由(1)也除尽a,所以r是a、b的公约数.反之,任何一除尽b的数,由(1),也除尽r,因此r是a、b的最大公约数. 如果r1≠0,则用r1除r得商a2,余数r2,即 r=a2r1+r2,0≤r2<r1.
(3) 如果r2=0,那么由(2)可知r1是b、r的公约数,由(1),r1也是a、b的公约数.反之,如果一数除得尽a、b,那末由(1),它一定也除得尽b、r,由(2),它一定除得尽r、r1,所以r1是a、b的最大公约数. 如果r2≠0,再用r2除r1,如法进行.由于b>r>r1>r2>…逐步小下来,而又都是正整数,因此经过有限步骤后一定可以找到a、b的最大公约数d(它可能是1).这就是有名的辗转相除法,在外国称为
欧几里得算法.