质数

质数（prime number）又称素数，有无限个。

一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。

根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。

最小的质数是2。

合数，数学用语，英文名为Composite number，指自然数中除了能被1和本身整除外，还能被其他的数整除（不包括0)的数。

与之相对的是质数（因数只有1和它本身，如2,3,5,7,11,13等等，也称素数）,而1既不属于质数也不属于合数。

最小的合数是4。

∙所有大于2的偶数都是合数。

∙所有大于5的奇数中，个位是5的都是合数。

∙最小的合数为4。

∙每一合数都可以以唯一形式被写成质数的乘积。

(算术基本定理)∙对任一大于5的合数。

(威尔逊定理)约数，又称因数。

整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。

a称为b的倍数，b称为a的约数。

在大学之前，"约数"一词所指的一般只限于正约数。

约数和倍数都是二元关系的概念，不能孤立地说某个整数是约数或倍数。

一个整数的约数是有限的。

同时，它可以在特定情况下成为公约数。

在自然数（0和正整数）的范围内，任何正整数都是0的约数。

4的正约数有：1、2、4。

6的正约数有：1、2、3、6。

10的正约数有：1、2、5、10。

12的正约数有：1、2、3、4、6、12。

15的正约数有：1、3、5、15。

18的正约数有：1、2、3、6、9、18。

20的正约数有：1、2、4、5、10、20。

注意：一个数的约数必然包括1及其本身。

枚举法枚举法：将两个数的因数分别一一列出，从中找出其公因数，再从公因数中找出最大的一个，即为这两个数的最大公因数。

例：求30与24的最大公因数。

30的正因数有：1,2,3,5,6,10,15,3024的正因数有：1,2,3,4,6,8,12,24易得其公因数中最大的一个是6，所以30和24的最大公因数是6。

短除法短除符号就像一个倒过来的除号，短除法就是先写出要求最大公因数的两个数A、B，再画一个短除号，接着在原本写除数的位置写两个数公有的质因数Z （通常从最小的质数开始），然后在短除号的下方写出这两个数被Z整除的商a，b，对a，b重复以上步骤，以此类推，直到最后的商互质为止，再把所有的除数相乘，其积即为A，B的最大公因数。

分解质因数将需要求最大公因数的两个数A，B分别分解质因数，再从中找出A求12和18的最大公约数、B公有的质因数，把这些公有的质因数相乘，即得A、B的最大公约数。

例：求48和36的最大公因数。

把48和36分别分解质因数：48=2×2×2×2×336=2×2×3×3其中48和36公有的质因数有2、2、3，所以48和36的最大公因数是2×2×3=12。

辗转相除法（欧几里得算法）对要求最大公因数的两个数a、b，设b<a，先用b除a，得a=bq+r1(0≤r1<b）。

若r1=0，则（a，b)=b；若r1≠0，则再用r1除b，得b=r1q+r2 (0≤r2<r1）.，若r2=0，则（a，b)=r1，若r2≠0，则继续用r2除r1……如此循环，直到能整除为止。

其最后一个非零余数即为（a，b）。

这一算法的证明如下：设两数为a、b(b<a），用gcd(a,b）表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，辗转相除法即是要证明gcd(a,b)=gcd(b,r）。

令c=gcd(a,b），则设a=mc，b=nc，根据前提有r =a-kb=mc-knc=(m-kn)c 由上，可知c也是r的因数，故可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公因数成为cd，而非c】所以 gcd(b,r)=c，继而gcd(a,b)=gcd(b,r）。

例：求8251和6105的最大公因数。

考虑用较大数除以较小数，求得商和余数：8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4最后除数37是148和37的最大公因数，也就是8251与6105的最大公因数。

约数也叫做因数，是因数的另一个称呼。

更相减损术更相减损术出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

其原文为：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。

以等数约之。

”翻译成现代语言就是第一步：任意给定两个正整数a、b；判断它们是否都是偶数。

若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。

继续这个操作，直到所得的减数和差相等为止。

这个数就是a、b的最大公约数。

例：求98与63的最大公因数。

分析：由于63不是偶数，把98和63以大数减小数，并辗转相减：98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98和63的最大公约数为7。

注：以上首三个方法同样适用于求多个自然数的最大公约数求约公式一般地，对自然数n进行分解质因数，设n可以分解为n=p⑴^α⑴·p⑵^α*⑵·…·p(k)^α（k)其中p⑴、p⑵、…p(k）是不同的质数，α⑴、α⑵、…α（k）约数个数求法公式是正整数，则形如n=p⑴^β⑴·p⑵^β*⑵·…·p(k)^β（k)的数都是n的约数，其中β⑴可取a⑴+1个值：0,1,2，…，α⑴；β⑵可取α⑵+1个值：0,1,2，…，α⑵…；β（k）可取a(k)+1个值：0,1,2，…，α（k).且n的约数也都是上述形式，根据乘法原理，n的约数共有（α⑴+1）（α⑵+1）…（α（k)+1）⑺个。

式⑺即为求一个数约数个数的公式。

负约数定义国内课本中，最先提到约数这个概念是在小学，而此时还没学负数。

等到学了负数，一般要直到大学数学系“初等数论”中才严格定义约数，那个时候就包括负约数了。

如果d|a并且d≥0，则我们说d是a的约数。

注意，d|a当且仅当（-d)|a，因此定义约数为非负整数不会失去一般性，只要明白a的任何约数的相应负数同样能整除a。

一个整数a的正约数最小为1，最大为|a|。

例题105的负约数的和是多少？105的所有负约数就是105的所有正约数的相反数所组成的集合。

105的正约数有1,3,5,7,15,21,35,105105的负约数有-1,-3,-5,-7,-15,-21,-35,-105其和为 -（1+3+5+7+15+21+35+105） = ﹣192100以内的自然数中，有6个约数的自然数有哪些？100以内的自然数中，有10个约数的自然数有哪些？两个数的和是50，它们的最大公约数是5，求这两个数最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。

求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。

与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。

基本概念如果数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的最小公倍数。