最大公约数
两个或多个整数共有的约数中最大的一个
条目
历史版本
最大公约数（Greatest Common Divisor，简称GCD）[1]，又称最大公因数、最大公因子，[3]是指两个或多个整数共有的约数中最大的一个。[2]整数序列
的最大公约数可以记为
或
。如果
，那么
叫做互素或互质。[4]求最大公约数常见的方法有分解质因数法、短除法、辗转相除法以及更相减损术。[9][10][11]两个整数
最大公约数和最小公倍数
的关系是
，两个整数的最大公约数与最小公倍数存在分配律：
；
。[12][13]
在中国古代的《九章算术》(约成书于东汉初年，公元1世纪)中，记载了古代中国人在算术方面的研究成果。因此可以认为最大公约数的概念至少在公元前2时期已经被古代中国数学家所熟知。[14]古希腊的数学家欧几里得（Euclid）的著作《几何原本》，在这本书也提到了最大公约数（公质数），欧几里得在这本书中主要研究了几何学的基础知识，也涉及了一些数论方面的内容。[15]最大公约数的简单办法是采用辗转相除法，这一方法最早见于欧几里得的《几何原本》和中国古算书《九章算术》中。[16][17]