[拼音]：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≤r
设α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的素数。埃拉托斯特尼筛法的改进和发展，是近代解析数论的重要工具之一。
顺天号
子美号
