最大公约数

最大公约数（Greatest Common Divisor，简称GCD），又称最大公因数、最大公因子，是指两个或多个整数共有的约数中最大的一个。整数序列的最大公约数可以记为或。如果，那么叫做互素或互质。求最大公约数常见的方法有分解质因数法、短除法、辗转相除法以及更相减损术。两个整数最大公约数和最小公倍数的关系是，两个整数的最大公约数与最小公倍数存在分配律：；。

在中国古代的《九章算术》(约成书于东汉初年，公元1世纪)中，记载了古代中国人在算术方面的研究成果。因此可以认为最大公约数的概念至少在公元前2时期已经被古代中国数学家所熟知。古希腊的数学家欧几里得（欧几里得）的著作《几何原本》，在这本书也提到了最大公约数（公质数），欧几里得在这本书中主要研究了几何学的基础知识，也涉及了一些数论方面的内容。最大公约数的简单办法是采用辗转相除法，这一方法最早见于欧几里得的《几何原本》和中国古算书《九章算术》中。

最大公约数可以应用在装修材料的选取方面，也可以提出基于最大公约数定理的QC-RA码构造方法；基于GCD定理进一步联合构造编码协作系统信源。

定义

设是n个整数，若整数是它们之中每一个的因数，那么就叫作的一个公约数，诸公因数中最大的一个叫作最大公因数，记作，如果，那么叫做互质或互质。若中每两个整数互质，就叫做两两互质。

示例

10有因数1,2,5,10；15有因数1,3,5,15，所以1是10和15的公因数，5也是10和15的公因数。

12和30的公因数有四个：1,2,3,6；在这四个数里最大的一个是6，6就叫做12和30的最大公因数。

如±1,±2,±3,±4,±6,±12都是72,60,48的公因数，12是72,60,48的最大公因数，即(72,60,48)=12。

如2,3,5两两互质，即(2,3)=(3,5)=(2,5)=1；再如6,8,9互质（6,8,9）=1，但并不两两互质，即(6,8)=2，(6,9)=3，(8,9)=1。

简史

已知两个非零整数a和b，简单的办法是采用辗转相除法，这一方法最早见于欧几里得的《原本》(公元前3世纪)，中国古算书《九章算术》(约成书于东汉初年，公元1世纪)也记有这一方法。《九章算术》作为中国数学史上的一部重要著作，记载了古人在算术方面的研究成果。这本书的成书时间可以追溯到公元前2世纪，因此可以认为最大公约数的概念至少在这个时期已经被古代中国数学家所熟知。古希腊的数学家欧几里得（欧几里得）（公元前330-275），他被称为“几何之父”，著作《几何原本》被称为最成功的教科书，在这本书也提到了最大公约数（公质数），欧几里得在这本书中主要研究了几何学的基础知识，但也涉及了一些数论方面的内容。他给出了一种辗转相除法的方法，用于计算两个数的最大公因数。

相关概念

整数

把叫作自然数，也叫作非负整数。所有自然数构成的集合，叫作自然数集，记作。

把叫作正整数。所有正整数构成的集合，叫作正整数集，记作。

把叫作负整数。所有负整数构成的集合，叫作负整数集，记作。

正整数、零、负整数统称为整数。所有整数构成的集合，叫作整数集，记作。

因数和倍数

设，且，如果存在整数，使，则称整除，或能被整除，记作。此时我们称为的因数(或约数)，为的倍数。换句话说，就是能被除尽(没有余数)，亦即除以的商为整数。可见，倍数相当于商式中的被除数，约数相当于商式中的除数。如果使的整数不存在(即除以的商不是整数)，则称不整除，或不能被整除，记作。如

按照以上定义，对任意整数，必有即1是任何整数的约数；任何非零整数必是自身的约数，也是自身的倍数；0是任何非零整数的倍数。

质数和合数

如果有两个正整数若，则称为的正因数。显然，数字1有且只有它本身一个正因数；2有且只有1和它本身两个正因数；而4除了1和它本身两个正因数之外，还有正因数2，即4的正因数的个数大于2。

一个大于1的正整数，若除了1和它本身之外没有其他正因数，则称这个正整数为质数(或素数)；否则称为合数。如都是质数；都是合数。

最小公倍数

定义设是个整数且，若是这个整数中每一个数的倍数，则就叫做这个整数的一个公倍数。在的一切公倍数中最小的正数叫做最小公倍数，记作

性质

若是任意n个不全为零的整数，()=()。

证明：设是的公约数，由可推出必有，即是的公因数；反之亦然，由此可知与的全体公因数集合相同。故

()=()。

交换律

若

证明：因为，所以，又因为，所以。

若。

证明：因为，所以。再因为，所以。又，所以，于是，因此定理成立。

分配律

若，则

证明：设，则故，是的一个公因数，而

同理可得

例如，由377=319X1+58，可得(319，377)=(319，58)。

结合律

最大公约数的结合律性质

设为任一正整数，那么

证明：由定理的最大公约数，存在，使可知存在使，又显然，则有：。

相关推论

定理1：若是任意个不全为零的整数，则

（i）与的公约数相同；

（ii）()=()。

证明：设是的任一公因数，由定义，因而，故是的一个公约数；同法可证，的任一个公因数都是的一个公因数。故与的公因数相同。

定理2：若是任一正整数，则（i）0与的公约数就是的因数；反之，的因数也就是0与的公因数；（ii）。

证明：0与的公因数就是的因数，由于任何非零整数都是0的因数，故的因数也就是的公因数，于是(i)获证；其

次，我们立刻知道的最大因数是；而的最大公因数是的最大因数，故。

定理3：设是任意三个不全为0的整数，且，其中是非零整数，则有相同的公因数，因而。

证明：设是的任一公因数，由定义，是的因数，因而是的一个公因数，

同法可证的任一公因数是的一个公约数，于是定理的前一部分获证；第二部分随之成立。

定理4：若是任意两个整数，则就是(1)中最后一个不等于零的余数，即。

证明：由定理2,3即得。

贝祖定理

贝祖(Bezout)定理：设是不全为零的整数，则存在整数，

使得，

证明，公约数，，由整除的性质,可知所以。

反过来，再由整除的性质，可知，即为的一个公因数，因此上述讨论表明现在利用欧几里得算法可知，依次用的线性组合表示出；用的线性组合表示出；最后用表示出。因此，使得(1)成立的整数存在。

如果，那么称互质，依上述定理结合整除的性质，可知，使得。

计算

辗转相除法（欧几里得算法）

带余数除法：若是两个整数，其中则存在着两个整数及，使得成立，而且及是唯一的。其中，叫做被除所得的不完全商，叫作被除所得到的余数。

证明：

作整数序列则必在上述序列的某两项之间，即存在一个整数使得成立。令，则，而。

辗转相除法可用以求出两个正整数的最大公因数。

设是任意两个正整数，由带余数除法，我们有下面的系列等式：

因为每进行一次带余数除法，余数就至少减一，而是有限的，所以我们最多进行次带余数除法，总可以得到一个余数是零的等式，即，(1)式所指出的计算方法，叫作辗转相除法。

证明：

若是任意两个整数，则就是（1）中最后一个不等于零的余数，即

由以上的讨论，我们可以看到，若两整数中有一为零，而 另一数不为零时，则为不等于零的数的绝对值，若两数都不是零时，则最大公因数可以由(1)实际地算出来。

更相减损术

更相减损术的具体内容是：如果分母、分子都是偶数，那么先除以2；如果不全是偶数，便将分子、分母互减，以少减多，直至得出最大公约数为止。用最大公约数去约分子、分母，便可使分数最简。

若都是正整数，且，如果，那么。

例如，求623，1424，801，1513四个数的最大公约数，可以不拘次序地挑选最方便的，从较大数中减去较小数，求其等数即可：(623，1424，801，1513)

=(623，1424-801，801-623，1513-1424)

=(623，623，178，89)

=(623-89x6，623-89x6，178-89，89)

=(89，89，89，89)=89。

扩展欧几里得算法

可以使用欧几里得算法来找到s，t，使得。

例如 GCD (35,27)：35=1*27+8 35-1*27=8

27=3*8+3 27-3*8 =3

8=2*3+2 8-2*3=2

3=1*2+1 3-1*2=1

2=2*1+0

皮耶·德·费玛（Fermat）大定理是费马于1637年左右在古希腊数学家丢番图(Diophantus)所著《算术》一书的空白处写下的注释，用如今的语言叙述，就是：不定方程没有正整数解。费马大定理是属于不定方程的。所谓不定方程，是指未知数的个数多于方程个数的方程(或方程组)。数论中的不定方程，通常对解的范围有一定的限制，例如解限制在有理数、整数等范围内。

分解质因数

把一个大于1的正整数表示成它的质因数之积的形式，叫作把这个正数分解质因数。

几个数的公约数是这几个数最大公因数的因数，由此和最大公因数的定义，我们可以得到求最大公因数的分解质因数法：

①写出各数的标准分解式；

②写出各分解式共同的质因数及其最小次方数，并把如此得到的幂写成连乘的形式。

例如：求(60，108，24)。

解。60=2²X3X5，108=2²X3³，24=2³X3，所以(60，108，24)-2²x3=12。

提取公因数（短除法）

根据最大公因数的结合律性质，可用逐步提取公因数的方法求几个数的最大公因数，

例求(162，216，378，108)。

解。

欧拉算法

利用辗转相除法求(5767，4453)，

因为5767=4453X1+1314，所以(5767，4453)=(4453，1314)；

因为4453=1314X3+511，所以(4453，1314)=(1314，511)；

因为1314=511X2+292，所以(1314，511)=(511，292)；

因为511=292X1+219，所以(511，292)-(292，219)；

因为292=219X1+73，所以(292，219)=(219，73)；

因为219-73X3+0，所以(219，73)=73。

所以(5767,4453)=73。

上述过程数据、符号书写重复太多，可以简化为下面的竖式：

欧拉给出了下面的方法，我们称之为欧拉算法，其步骤如下：

(1)竖式中最后一个商不要，将其余的商按相反次序排成一行:写在横线上方；

(2)在横线下方，对齐横线上方左数第一个商:写，在的左边写数1；

(3)用横线上方左数第二个商按箭头所示方向乘，再加左侧箭头所指向的数值1，把所得结果对齐写在横线下方，以下各步仿照上一步进行，直到算写完毕为止。

应用

生活方面

解决装修材料的问题

一块钢板，长135cm，宽105cm。现在把它截成同样大小的正方形，正方形要最大的，并且不许剩下钢板，求正方形的边长。

解：因为正方形要最大的，所以就要求正方形最大的边长是多少。要求正方形最大的边长，就要求135cm和105cm的最大公因数。求出(135,105)=15。所以，选取15cm的正方形钢板最适合。

计算机方面

判断二元一次不定方程是否存在整数解

二元一次不定方程的表达式如下：其中均为已知整数，要判断该方程式是否存在整数解，首先要利用辗转相除法求得与的最大公约数，然后按照进行计算，判断能否将与的最大公约数整除，如果计算得到的余数为0，则说明方程式存在整数解，且整数解的数量为无数多个；如果计算得到的余数不为0，说明方程式不存在整数解，即整数解的个数为0。

例：a)判断方程式28X+12Y=200是否存在整数解。

(b)判断方程式2X+4Y=1是否存在整数解。

具体计算过程如下:(a)首先利用辗转相除法计算28和12存在的最大公约数，28÷12=2------4.此时余数不为0，因此继续列式计算“12÷4=3”，此时余数为0，也就是说28与12存在的最大公约数为4。然后列式计算“200÷4-50”，余数为0证明方程式28X+12Y=200存在整数解，且整数解的数量为无数个。(b)同样先利用辗转相除法计算2和4的最大公约数，4÷2=2，余数为0。因此2与4的最大公约数为2。再通过式子1÷2的计算结果，判断出1不能够将2整除，因此方程式2X+4Y=1不存在整数解。

编码协作系统

准循环重复累积(Quasi-Cyclic Repeat Accumulate，QC-RA)码具有准循环低密度奇偶校验(Low 密度 Parity Check,LDPC)码的优点，同时能实现差分编码且为系统码，非常适用于编码协作系统。首先，提出基于最大公约数(Greatest Common Divisor,GCD)定理的QC-RA码构造方法；然后，进一步基于GCD定理联合构造编码协作系统信源节点与中继节点采用的QC-RA码，并从理论上证明基于该联合构造方法得到的编码协作系统QC-RA码无girth-4.girth-6环。仿真结果表明，采用QC-RA码的编码协作系统相对于点对点系统具有明显的性能增益；同时，与采用大列重构造QC-RA的编码协作相比，采用文中基于GCD定理联合构造的QC-RA码的编码协作误码率性能更加优异。

参考资料

最大公约数.术语在线.2023-10-18

最小公倍数.术语在线.2023-10-18

Foundations of Computing 1.Microsoft PowerPoint - lecture13.2023-10-28