词条 | 整除 |
释义 | zhengchu 整除(卷名:数学) divisibility 数论中一个最基本的概念。任给二整数α与b,其中b≠0,如果有一个整数с使 α=bс,就称b能整除α,记作b│α。此时把b叫作α的因数,α叫作b的倍数。如果b不能整除α,就记作b ![]() ![]() 最大公因数与辗转相除法 设α1,α2,…,αn(n≥2)是n个整数,若整数d>0是它们之中每一个的因数,那么d就叫作α1,α2,…,αn的一个公因数,诸公因数中最大的一个叫作最大公因数,记作 (α1,α2,…,αn)。如果(α1,α2)=1,那么α1和α2叫做互素或互质。设α、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可惟一地分解成标准形式 ![]() ![]() ![]() ![]() ![]() 如何把一个给定的大的正整数分解为它的标准形式,一直是人们所关心和研究的问题,它不仅具有理论意义,而且有实际应用。虽然已经得到一些较有效的算法来判断一个大数是否素数,但是分解一个大数,仍然十分困难,即使借助于电子计算机也要花费惊人的时间。利用大数分解的困难性,1977年,R.L.里弗斯特等人设计出一种能够公开密钥的密码。 埃拉托斯特尼筛法 大约在公元前250年,古希腊数学家埃拉托斯特尼提出一个造出不超过N 的素数表的方法,它基于这样一个简单的性质:如果n≤N,而n是复合数,则n必为一不大于 ![]() ![]() ![]() |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。