什么是公因數(shù)與最大公因數(shù)

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

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

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

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

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

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

最大公因數(shù)

定義

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

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

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

幾個(gè)自然數(shù)公有的倍數(shù)，叫做這幾個(gè)數(shù)的公倍數(shù)，其中最小的一個(gè)自然數(shù)，叫做這幾個(gè)數(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。若干個(gè)互質(zhì)數(shù)的最小公倍數(shù)為它們的乘積的絕對(duì)值。

求法

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

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

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

短除法

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

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

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

輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法是求兩個(gè)自然數(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。

可以寫(xiě)成右邊的格式。

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