最大公約數（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、16的公約數有1、2、4，其中最大的一個是4，4是12與16的最大公約數，一般記為（12，16）=4。
如±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)實際地算出來。
更相減損術
更相減損法，也叫更相減損術，是出自《九章算術》的一種求最大公約數的算法，它原本是為約分而設計的，但它適用于任何需要求最大公約數的場合。數學語言表達為：當 a > b 時有 gcd(a,b) = gcd(a - b,b)。不斷用較大數減去較小數，直到兩數相等，此時結果即為最大公約數。用最大公約數去約分子、分母，便可使分數最簡。
若都是正整數，且，如果，那么。
例如，求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，使得。
例如，求（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。
皮耶·德·費瑪（Fermat）大定理是費馬于1637年左右在古希臘數學家丟番圖(Diophantus)所著《算術》一書的空白處寫下的注釋，用如今的語言敘述，就是：不定方程沒有正整數解。費馬大定理是屬于不定方程的。所謂不定方程，是指未知數的個數多于方程個數的方程(或方程組)。數論中的不定方程，通常對解的范圍有一定的限制，例如解限制在有理數、整數等范圍內。
分解質因數
把一個大于1的正整數表示成它的質因數之積的形式，叫作把這個正數分解質因數。
幾個數的公因數是這幾個數最大公因數的因數，由此和最大公因數的定義，我們可以得到求最大公因數的分解質因數法：
①寫出各數的標準分解式；
②寫出各分解式共同的質因數及其最小次方數，并把如此得到的冪寫成連乘的形式。
例如：求24和60的最大公約數。
解。先分解質因數，得24=2×2×2×3，60=2×2×3×5。24與60的全部公有的質因數是2、2、3，它們的積是2×2×3=12，所以（24，60）=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