最大公约数（Greatest Common Divisor，简写为G.C.D.；或Highest Common Factor，简写为H.C.F.），指某几个整数共有约数中最大的一个。
两个整数的最大公约数主要有三种寻找方法：
和最小公倍数（L.C.M.）的关系： 
两个整数的最大公约数可用于计算两数的最小公倍数，或分数化简成最简分数。
两个整数的最大公约数和最小公倍数中存在分配律：
在座标里，将点（0, 0）和（a, b）连起来，通过整数座标的点的数目（除了（0, 0）一点之外）就是G.C.D.(a, b)。
辗转相除法
在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。
算法描述
计算过程
function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
在欧几里得定义的减法版本，取余运算被减法替换。
function gcd(a, b)
if a = 0
return b
while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a
递归版本：
function gcd(a, b)
if b = 0
return a
else
return gcd(b, a mod b)
除了辗转相除法之外，也有一些高效的算法存在，如二进制最大公约数算法将除法操作替换成了二进制的移位，以进一步提高用计算机运算时的效率。但是，这种改变并没有降低算法的复杂度（仍然是O(h²)），虽然它在计算机上确实比辗转相除法快些。也可以通过只检查a和b的前几位数来进一步提高效率，不过效果并不明显。二进制版的算法还可以扩展到其它进制，效率最多可以提升五倍。
另外，最小公倍数 = A*B/最大公约数
