最大公约数
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
中文名最大公因数外文名GreatestCommonDivisor(***)别名HighestCommonFactor(HCF)所属学科数学
基本概念编辑
如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数和倍数都表示一个整数与另一个整数的关系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。
“倍“与“倍数“是不同的两个概念，“倍“是指两个数相除的商，它可以是整数、小数或者分数。“倍数“只是在数的整除的范围内，相对于“约数“而言的一个数字的概念，表示的是能被某一个自然数整除的数。
几个整数，公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）=4。12、15、18的最大公约数是3，记为（12，15，18）=3。
几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数。例如：4的倍数有4、8、12、16，……，6的倍数有6、12、18、24，……，4和6的公倍数有12、24，……，其中最小的是12，一般记为[4，6]=12。12、15、18的最小公倍数是180。记为[12，15，18]=180。若干个互质数的最小公倍数为它们的乘积的绝对值。
求法编辑
质因数分解法
质因数分解
质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。
例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。
把几个数先分别分解质因数，再把各数中的全部公有的质因数和独有的质因数提取出来连乘，所得的积就是这几个数的最小公倍数。
例如：求6和15的最小公倍数。先分解质因数，得6=2×3，15=3×5，6和15的全部公有的质因数是3，6独有质因数是2，15独有的质因数是5，2×3×5=30，30里面包含6的全部质因数2和3，还包含了15的全部质因数3和5，且30是6和15的公倍数中最小的一个，所以[6，15]=30。
短除法
短除法：短除法求最大公约数，先用这几个数的公约数连续去除，一直除到所有的商互质为止，然
后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。
短除法求最小公倍数，先用这几个数的公约数去除每个数，再用部分数的公约数去除，并把不能整除的数移下来，一直除到所有的商中每两个数都是互质的为止，然后把所有的除数和商连乘起来，所得的积就是这几个数的最小公倍数，例如，求12、15、18的最小公倍数。
短除法的格式
短除法的本质就是质因数分解法，只是将质因数分解用短除符号来进行。
短除符号就是除号倒过来。短除就是在除法中写除数的地方写两个数共有的质因数，然后落下两个数被公有质因数整除的商，之后再除，以此类推，直到结果互质为止（两个数互质）。
而在用短除计算多个数时，对其中任意两个数存在的因数都要算出，其它没有这个因数的数则原样落下。直到剩下每两个都是互质关系。
求最大公因数便乘一边，求最小公倍数便乘一圈。
无论是短除法，还是分解质因数法，在质因数较大时，都会觉得困难。这时就需要用新的方法。
辗转相除法
古希腊数学家欧几里德
辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。
这就是辗转相除法的原理。
辗转相除法的格式
例如，求（319，377）：
∵319÷377=0（余319）
∴（319，377）=（377，319）；
∵377÷319=1（余58）
∴（377，319）=（319，58）；
∵319÷58=5（余29），
∴（319，58）=（58，29）；
∵58÷29=2（余0），
∴（58，29）=29；
∴（319，377）=29.
可以写成右边的格式。
用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。
更相减损法
刘徽《九章算术》
更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
例1、用更相减损术求98与63的最大公约数。
解：由于63不是偶数，把98和63以大数减小数，并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公约数等于7。
这个过程可以简单的写为：
（98，63）=（35，63）=（35，28）=（7，28）=（7，21）=（7，14）=（7，7）=7.
例2、用更相减损术求260和104的最大公约数。
解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。
此时65是奇数而26不是奇数，故把65和26辗转相减：
65-26=39
39-26=13
26-13=13
所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。
这个过程可以简单地写为：
（260，104）=（65，26）=（39，26）=（13，26）=（13，13）=13.[1]
比较辗转相除法与更相减损术的区别
（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。[2-3]
常用结论编辑
在解有关最大公约数、最小公倍数的问题时，常用到以下结论：
（1）如果两个自然数是互质数，那么它们的最大公约数是1，最小公倍数是这两个数的乘积。
例如8和9，它们是互质数，所以（8，9）=1，[8，9]=72。
（2）如果两个自然数中，较大数是较小数的倍数，那么较小数就是这两个数的最大公约数，较大数就是这两个数的最小公倍数。
例如18与3，18÷3=6，所以（18，3）=3，[18，3]=18。
（3）两个整数分别除以它们的最大公约数，所得的商是互质数。
例如8和14分别除以它们的最大公约数2，所得的商分别为4和7，那么4和7是互质数。
（4）两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。
例如12和16，（12，16）=4，[12，16]=48，有4×48=12×16，即（12，16）×[12，16]=12×16。
（5）***(a，b)isthesmallestpositivelinearcombinationofaandb.a与b的最大公约数是最小的a与b的正线性组合，即对于方程xa+yb=c来说，若x，a，y，b都为整数，那么c的最小正根为gcd(a，b).
历史发展编辑
古希腊数学家欧多克斯
在求解最大公约数的几种方法中，辗转相除法最为出名。辗转相除法是目前仍然在使用的历史最悠久的算法之一。它首次出现于几何原本（卷7命题1–2、卷10命题2–3）（大约公元前300年）。在卷7中用于整数，在卷10中用于线段的长度（也就是现在所说的实数，但是当时未有实数的概念）。卷10中出现的算法是几何的，两段线段a和b的最大公约数是准确测量a和b的最大长度。
这个算法可能并非欧几里得发明，而仅仅是将先人的结果编进他的几何原本。数学家、历史学家范德瓦尔登认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。辗转相除法可能是被大约公元前375年的欧多克斯发现的，但也有可能更早之前就已经存在，因为欧几里得和亚里士多德的著作中都出现了?νθυφα?ρεσι?一词（anthyphairesis，意为“辗转相减”），
最小公倍数
最小公倍数（LeastCommonMultiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个整数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。
基本概况
最小公倍数（LeastCommonMultiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个整数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。其中，4是最小的公倍数，叫做他们的最小公倍数。例如，十天干和十二地支混合称呼一阴历年，干支循环回归同一名称的所需时间，就是12和10的最小公倍数，即是60──一个“甲子”。对分数进行加减运算时，要求两数的分母相同才能计算，故需要通分；假如令两个分数的分母通分成最小公倍数，计算量便最低。
方法
短除法
步骤：一、找出两数的最小公约数，列短除式，用最小约倍数去除这两个数，得二商；二、找出二商的最小公约数，用最小公约数去除二商，得新一级二商；三、以此类推，直到二商为互质数；四、将所有的公约数及最后的二商相乘，所得积就是原二数的最小公倍数。例：求48和42的最小公倍数解：48与42的最小公约数为248/2=24；42/2=21；24与21的最小公约数为324/3=8；21/3=7；8和7互为质数2×3×8×7=336
质因数分解
举例：12和27的最小公倍数12=2×2×327=3×3×3必须用里面数字中的最大次方者，像本题有3和3的立方，所以必须使用3的立方(也就是3*3*3)，不能使用3所以：2×2×3×3×3=4×27=108两数的最小公倍数是108
借助最大公约数求最小公倍数
步骤：一、利用辗除法或其它方法求得最大公约数；二、最小公倍数等于两数之积除以最大公约数。举例：12和8的最大公约数为412×8/4=24两数的最小公倍数是24注：公约数又称公因数。
示例
例题1
两个数的最大公因数是15，最小公倍数是90，求这两个数分别是多少？
15×1=15，15×6=90；当a1b1分别是2和3时，a、b分别为15×2=30，15×3=45。所以，这两个数是15和90或者30和45。
例题2
两个自然数的积是360，最小公倍数是120，这两个数各是多少？上！！
分析我们把这两个自然数称为甲数和乙数。因为甲、乙两数的积一定等于甲、乙两数的最大公因数与最小公倍数的积。根据这一规律，我们可以求出这两个数的最大公因数是360÷120=3。又因为（甲÷3=a，乙÷3=b)中，3×a×b=120，a和b一定是互质数，所以，a和b可以是1和40，也可以是5和8。当a和b是1和40时，所求的数是3×1=3和3×40=120；当a和b是5和8时，所求的数是3×5=15和3×8=24。
例题3
甲、乙、丙三人是朋友，他们每隔不同天数到图书馆去一次。甲3天去一次，乙4天去一次，丙5天去一次。有一天，他们三人恰好在图书馆相会，问至少再过多少天他们三人又在图书馆相会？
分析从第一次三人在图书馆相会到下一次再次相会，相隔的天数应该是3、4、5的最小公倍数。因为3、4、5的最小公倍数是60，所以至少再过60天他们三人又在图书馆相会。
例题4
一块砖长20厘米，宽12厘米，厚6厘米。要堆成正方体至少需要这样的砖头多少块？
分析把若干个长方体叠成正方体，它的棱长应是长方体长、宽、高的公倍数。现在要求长方体砖块最少，它的棱长应是长方体长、宽、高的最小公倍数，求出正方体棱长后，再根据正方体与长方体体积之间的关系就能求出长方体砖的块数。
例题5
甲每秒跑3米，乙每秒跑4米，丙每秒跑2米，三人沿600米的环形跑道从同一地点同时同方向跑步，经过多少时间三人又同时从出发点出发？
分析甲跑一圈需要600÷3=200秒，乙跑一圈需要600÷4=150秒，丙跑一圈需要600÷2=300秒。要使三人再次从出发点一齐出发，经过的时间一定是200、150和300的最小公倍数。200、150和300的最小公倍数是600，所以，经过600秒后三人又同时从出发点出发。
应用实例
分元宝
亡故的先父留下遗嘱，
共有遗产17个元宝，
老大得元宝的二分之一、17/2=8.5
老二得元宝的三分之一、17/3=5.66666
老三得元宝的九分之一、17/9=1.8
问他们每一个人分别应该分几个元宝？
在《一代大商孟洛川》中是这样做的
孟洛川拿来一个元宝加上去
好了，开始分元宝
答案是：老大9个元宝、老二6个元宝、老三2个元宝。
还剩下一个元宝，是我们孟洛川的，拿回来
很不可思议吧
很简单的初中数学题老大分1/2，老二分1/3，老三分1/9
这三个数的最小公倍数就是18，即9/18+6/18+2/18=17/18，就是说他们老爷子给的这个比例和根本就没到1，。即1-17/18=1/18，也就是说，直接分，那是分不完17元宝的。这样这要用18这个最小公倍数就能分开，最后还剩一个
