公因數(shù)，亦稱“公約數(shù)”。它是一個能被若干個整數(shù)同時均整除的整數(shù)。如果一個整數(shù)同時是幾個整數(shù)的因數(shù)，稱這個整數(shù)為它們的“公因數(shù)”；公因數(shù)中最大的稱為最大公因數(shù)。

對任意的若干個正整數(shù)，1總是它們的公因數(shù)。

給定若干個整數(shù)，如果有一個(些)數(shù)是它們共同的因數(shù)，那么這個(些)數(shù)就叫做它們的公因數(shù)。而全部公因數(shù)中最大的那個，稱為這些整數(shù)的最大公因數(shù)。

公約數(shù)與公倍數(shù)相反，就是既是A的約數(shù)同時也是B的約數(shù)的數(shù)，12和15的公約數(shù)有1，3，最大公約數(shù)就是3。再舉個例子，30和40，它們的公約數(shù)有1，2，5，10，最大公約數(shù)是10。

公因數(shù)，又稱公約數(shù)。在數(shù)論的敘述中，如果n和d都是整數(shù)，而且存在某個整數(shù)c，使得n = cd，就說d是n的一個因數(shù)，或說n是d的一個倍數(shù)，記作d|n（讀作d整除n）。如果d|a且d|b，我們就稱d是a和b的一個公因數(shù)。根據(jù)裴蜀定理，對每一對整數(shù)a，b，都有一個公因數(shù)d，使得d = ax+by，其中x和y是某些整數(shù)，并且a和b的每一個公因數(shù)都能整除這個d。于是d的絕對值叫做最大公因數(shù)。

求幾個整數(shù)的最大公因數(shù)，只要把它們的所有共有的質(zhì)因數(shù)連乘，所得的積就是它們的最大公因數(shù)。

最大公因數(shù)

定義

如果數(shù)a能被數(shù)b整除，a就叫做b的倍數(shù)，b就叫做a的約數(shù)。約數(shù)和倍數(shù)都表示一個整數(shù)與另一個整數(shù)的關(guān)系，不能單獨存在。如只能說16是某數(shù)的倍數(shù)，2是某數(shù)的約數(shù)，而不能孤立地說16是倍數(shù)，2是約數(shù)。

"倍"與"倍數(shù)"是不同的兩個概念，"倍"是指兩個數(shù)相除的商，它可以是整數(shù)、小數(shù)或者分數(shù)。"倍數(shù)"只是在數(shù)的整除的范圍內(nèi)，相對于"約數(shù)"而言的一個數(shù)字的概念，表示的是能被某一個自然數(shù)整除的數(shù)。

幾個整數(shù)，公有的約數(shù)，叫做這幾個數(shù)的公約數(shù)；其中最大的一個，叫做這幾個數(shù)的最大公約數(shù)。例如：12、16的公約數(shù)有1、2、4，其中最大的一個是4，4是12與16的最大公約數(shù)，一般記為（12，16）=4。12、15、18的最大公約數(shù)是3，記為（12，15，18）=3。

幾個自然數(shù)公有的倍數(shù)，叫做這幾個數(shù)的公倍數(shù)，其中最小的一個自然數(shù)，叫做這幾個數(shù)的最小公倍數(shù)。例如：4的倍數(shù)有4、8、12、16，……，6的倍數(shù)有6、12、18、24，……，4和6的公倍數(shù)有12、24，……，其中最小的是12，一般記為[4，6]=12。12、15、18的最小公倍數(shù)是180。記為[12，15，18]=180。若干個互質(zhì)數(shù)的最小公倍數(shù)為它們的乘積的絕對值。

求法

質(zhì)因數(shù)分解法

把幾個數(shù)先分別分解質(zhì)因數(shù)，再把各數(shù)中的全部公有的質(zhì)因數(shù)和獨有的質(zhì)因數(shù)提取出來連乘，所得的積就是這幾個數(shù)的最小公倍數(shù)。

例如：求6和15的最小公倍數(shù)。先分解質(zhì)因數(shù)，得6=2×3，15=3×5，6和15的全部公有的質(zhì)因數(shù)是3，6獨有質(zhì)因數(shù)是2，15獨有的質(zhì)因數(shù)是5，2×3×5=30，30里面包含6的全部質(zhì)因數(shù)2和3，還包含了15的全部質(zhì)因數(shù)3和5，且30是6和15的公倍數(shù)中最小的一個，所以[6，15]=30。

短除法

短除法：短除法求最大公約數(shù)，先用這幾個數(shù)的公約數(shù)連續(xù)去除，一直除到所有的商互質(zhì)為止，然后把所有的除數(shù)連乘起來，所得的積就是這幾個數(shù)的最大公約數(shù)。短除法的本質(zhì)就是質(zhì)因數(shù)分解法，只是將質(zhì)因數(shù)分解用短除符號來進行。

短除符號就是除號倒過來。短除就是在除法中寫除數(shù)的地方寫兩個數(shù)共有的質(zhì)因數(shù)，然后落下兩個數(shù)被公有質(zhì)因數(shù)整除的商，之后再除，以此類推，直到結(jié)果互質(zhì)為止（兩個數(shù)互質(zhì)）。

而在用短除計算多個數(shù)時，對其中任意兩個數(shù)存在的因數(shù)都要算出，其它沒有這個因數(shù)的數(shù)則原樣落下。直到剩下每兩個都是互質(zhì)關(guān)系。求最大公因數(shù)便乘一邊，求最小公倍數(shù)便乘一圈。無論是短除法，還是分解質(zhì)因數(shù)法，在質(zhì)因數(shù)較大時，都會覺得困難。這時就需要用新的方法。

輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法是求兩個自然數(shù)的最大公約數(shù)的一種方法，也叫歐幾里德算法。

這就是輾轉(zhuǎn)相除法的原理。

例如，求（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。

可以寫成右邊的格式。

用輾轉(zhuǎn)相除法求幾個數(shù)的最大公約數(shù)，可以先求出其中任意兩個數(shù)的最大公約數(shù)，再求這個最大公約數(shù)與第三個數(shù)的最大公約數(shù)，依次求下去，直到最后一個數(shù)為止。最后所得的那個最大公約數(shù)，就是所有這些數(shù)的最大公約數(shù) 。