[拼音]：zhengchu

[外文]：divisibility

数论中一个最基本的概念。任给二整数α与b，其中b≠0，如果有一个整数с使 α=bс，就称b能整除α，记作b│α。此时把b叫作α的因数，α叫作b的倍数。如果b不能整除α，就记作bα。通常，因数总假定是正的。从整除的定义出发，以下一些性质是明显的：

（1）若b│α，с│b，则с│α；

（2）若b│α，则сb│сα，反之亦然；

（3）若с│α，с│b，则对任意的整m，n，有с│mα+nb；

（4）若b｜α，则。一般地，有所谓的带余除法，即设α、b是二整数，其中b>0，则存在两个惟一的整数q和r，使得α=bq+r，0≤rb=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是任意二正整数，则：

（1）α、b的所有公倍数就是[α，b)]的所有倍数；

（2）[α，b](α，b)=αb。

正整数可以分成三类；①1，只有正整数1是它的因数；

（2）素数p，p>1，只有正整数1和p是它的因数；

（3）复合数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

如何把一个给定的大的正整数分解为它的标准形式，一直是人们所关心和研究的问题，它不仅具有理论意义，而且有实际应用。虽然已经得到一些较有效的算法来判断一个大数是否素数，但是分解一个大数，仍然十分困难，即使借助于电子计算机也要花费惊人的时间。利用大数分解的困难性，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的素数。埃拉托斯特尼筛法的改进和发展，是近代解析数论的重要工具之一。

严正声明：本文由历史百科网注册或游客用户志专自行上传发布关于» 整除的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：志专；本文链接：https://www.freedefine.cn/wenzhan/129552.html