整除(卷名：数学)
divisibility
数论中一个最基本的概念。任给二整数α与b，其中b≠0，如果有一个整数с使 α=bс，就称b能整除α，记作b│α。此时把b叫作α的因数，α叫作b的倍数。如果b不能整除α，就记作b
α。通常，因数总假定是正的。从整除的定义出发，以下一些性质是明显的:①若b│α，с│b，则с│α;②若b│α，则сb│сα，反之亦然；③若с│α，с│b，则对任意的整m，n，有с│mα+nb；④若b｜α，则
。一般地，有所谓的带余除法，即设α、b是二整数，其中b>0，则存在两个惟一的整数q和r，使得α=bq+r，0≤r<b，r叫作α被b除所得到的余数，记为<α>b=r显然，b)整除α当且仅当r=0。最大公因数与辗转相除法 设α1，α2，…，αn(n≥2)是n个整数，若整数d>0是它们之中每一个的因数，那么d就叫作α1，α2，…，αn的一个公因数，诸公因数中最大的一个叫作最大公因数，记作 (α1，α2，…，αn)。如果(α1，α2)=1，那么α1和α2叫做互素或互质。设α、b是任意两个正整数，由带余除法可得下列诸式：
因为b>r1>r2>…，故经有限步之后，rn+1=0，且(α，b)=rn。这就叫做辗转相除法，又称欧几α2，…，αn的一个公倍数，所以最小公倍数总是存在的。设α、b是任意二正整数，则:①α、b的所有公倍数就是[α，b)]的所有倍数；②[α，b](α，b)=αb。素数和算术基本定理 正整数可以分成三类；①1，只有正整数1是它的因数；②素数p，p>1，只有正整数1和p是它的因数；③复合数m，有大于1同时小于m的因数。欧几里得证明了素数的个数是无限的。因为，如果素数有限，设为p1，p2，…，pk而整数p1，p2，…pk+1中必有不同于 p1，p2，…，pk的素因数。他还证明了若素数p│αb，则p│α或p│b。由此可得算术基本定理:任一大于1的整数数n，如果不计顺序，那么只有惟一的方法表示成素数的乘积里得算法，它是古希腊数学家欧几里得于公元前 4世纪给出的。他还证明了存在二整数l和m使得(α，b))=lα+mb)。显然，α、b)的任何公因数是(α，b)的因数。
最小公倍数 设α1，α2，…，αn(n≥2)是 n个正整数，如果m是这n个数中每一个数的倍数，那么m 就叫做这n个数的一个公倍数，一切公倍数中最小的正整数叫做最小公倍数，记为[α1，α2，…，αn]。因为乘积α1α2…αn就是α1，。由这个定理可知，任一大于1的整数n可惟一地分解成标准形式
，其中p1<p2<…<pk是素数。作为算术基本定理一个简单而直接的应用，设
，则
，其中
。多于两个正整数的最大公因数和最小公倍数可以仿此求出。算术基本定理又叫整数的惟一分解定理，是数论中一个基本的定理，许多结果依赖于它的成立。代数数论研究的主要问题之一，就是研究在给定的代数数域中代数整数的惟一分解定理是否成立。如何把一个给定的大的正整数分解为它的标准形式，一直是人们所关心和研究的问题，它不仅具有理论意义，而且有实际应用。虽然已经得到一些较有效的算法来判断一个大数是否素数，但是分解一个大数，仍然十分困难，即使借助于电子计算机也要花费惊人的时间。利用大数分解的困难性，1977年，R.L.里弗斯特等人设计出一种能够公开密钥的密码。
埃拉托斯特尼筛法 大约在公元前250年，古希腊数学家埃拉托斯特尼提出一个造出不超过N 的素数表的方法，它基于这样一个简单的性质:如果n≤N，而n是复合数，则n必为一不大于
的素数所整除。具体作法如下：先列出不超过的全体整数，设为
，然后依次排列2，3，…，N，在其中留下p1=2，而把p1的倍数全划掉，再留下p2，而把p2的倍数全划掉，继续如此往下做，直到最后留下pr而划去pr的倍数。所留下的整数就是不超过N 的全体素数。这就是著名的埃拉托斯特尼筛法。近代素数表都是由此法略加变化造出。1914年，D.H.莱默尔发表了1到10006721的素数表。1951年，J.P.库利克等又增加了从10006721到10999997间的素数。最大的素数表是D.B.扎盖尔1977年发表的，列出了不超过5×107的素数。埃拉托斯特尼筛法的改进和发展，是近代解析数论的重要工具之一。