最大公因数，指两个或多个整数共有约数中最大的一个。以下是一个用辗转相除法求最大公因数的例子：
求18和24的最大公因数。
用较大数除以较小数得到商和余数：
24div18=1ldots6，其中6是余数。
再用除数和余数做除法运算：
18div6=3，余数为0。
当余数为0时，此时的除数6就是原来两个数的最大公因数。
因此，18和24的最大公因数是6。
辗转相除法是求最大公因数的一种算法，它的原理是：用较大数除以较小数得到商和余数，再用除数和余数做除法运算，当余数为0时，此时的除数就是原来两个数的最大公因数。
一、定义
定义：给定两个整数a，b,必有公共的因数，叫做它们的公因数，当a,b不全部为0时，在有限个公因数中最大的那个叫做a、b的最大公因数，记作(a,b)
二、一种方法——辗转相除法
描述：设a,b为任意两个整数，且b不为0，应用带余除法，以b除a,得到商q1,余数r1；如果余数r1不为0，以r1除b，得到商q2，余数r2;如果r2不等于0，以r2除r1,如此继续下去，在有限个除法后，必然得到rn不为0且整除rn-1。

三、最大公约数的性质
关于最大公约数有一条重要的性质，这条性质在求解一次同余方程和不定方程时经常遇到。
1)

证明：不妨设b>0,用b除a,则有a = b*q1 + r1,
若r1 = 0,(a,b) = (b,r1) = b;所以(a,b) = a * 0 + b * 1
若r1 != 0,用r1除b;b = r1 * q2 + r2,
若r2 = 0,(a,b) = (b,r1) = (r1,r2) = r1 = a - b * q1;所以(a,b) = a * 0 + b * (-q1)
若r2 != 0,用r2 除r1;r1 = r2 * q3 + r3.
若r3 = 0,(a,b) = (r2,r3) = r2 = b - r1 * q2 = b - (a - b * q1) * q2;所以(a,b) = a * (-q2) + b * (1 + q1 * q2)
若r3 != 0,用r3 除r2........
由于最大公因数一定存在，所以一定可以经过有限次 得到rn = 0,所以这样的m,n一定存在且可以求出来。
2）由上面那条性质，可以推出整数的一条性质

证明：因为（a,b） = 1，所以存在整数m,n,使得am + bn = (a,b) = 1,
于是(ac)m + (bc)m = c
因为a | ac,a | bc，所以a | (ac)m + (bc)m,即a | c
