4.1 素数
本章目录 · 1 节
本章导读
本章在整数范围内讨论整除、素数、最大公因数、同余及其计算应用。若 ,存在整数 使 ,则称 整除 ,记 ;否则记 。因子若不特别说明,通常考察正因子。大于1的正整数的1和自身称平凡因子,其余正因子称真因子。例如10的正因子为1、2、5、10,真因子为2、5。
带余除法:对整数 和非零整数 ,存在唯一整数 使 ,其中 。余数记 。例如 ,,所以 ;带余除法中的非负余数约定,可能与某些程序语言对负数的余数操作不同。 当且仅当余数为0。
命题4.1.1概括整除性质:(1)若 ,则对任意整数 ,有 ;(2)若 ,则 ;(3)若 ,则 当且仅当 ;(4)若 ,则 ;(5)若 ,则 。证明分别把被整除的数写成整数倍,利用线性组合、倍数相乘、非零因子的消去及非零整数倍的绝对值至少为1得到。整除符号在这里均要求除数不为0。
定义4.1.1:大于1的正整数,若正因子只有1与自身,称素数或质数;否则称合数。1既不是素数也不是合数,0和负整数也不按本定义归入这两类。
命题4.1.2:(1)素数 的正因子若大于1,只能等于 ;(2)若素数 ,则 或 ;(3) 为合数当且仅当能写成 且 ;(4)合数必有素因子。第二项可用后文贝祖等式证明:若 ,则 ,存在 ,乘 后两项均被 整除,故 。推广到有限个因子的乘积时,至少一个因子被 整除。这里“素数”不能省掉,例如 ,但6不整除4或9。
定理4.1.1(算术基本定理):每个整数 都能唯一分解为互不相同素数的正整数次幂之积,除因子次序外无歧义:。存在性可用对 的强归纳:若非素数便拆成两个更小正整数,再分别分解;唯一性由素数整除乘积必整除其中一个因子,逐个消去相同素因子得到。
教材给出的分解为 ,,,,。为统一多个整数的素因子集合,可以允许某些指数为0,但此时必须固定所用素数列表,才有确定的指数表示。
推论4.1.1:若 ,则正因子恰为 ,其中每个 。各指数可以独立选择,所以正因子总数为 。
【例4.1.1】(1)99099有多少正因子?(2) 的二进制表示末尾有多少个连续0?
解:(1)由上述分解,正因子数为 。(2)二进制末尾0数等于素因子2的指数,不是十进制末尾0数。把所有2、4、8、16的贡献逐层计数,得到 ,所以有18个连续0。
定理4.1.2:素数有无穷多个。若全部素数只有 ,考察 ,它不被其中任意素数整除;但 必有素因子,得到矛盾。不要误以为 本身总是素数;证明只需要它具有名单之外的素因子。
令 为不超过 的素数个数。。定理4.1.3(素数定理)说明 。按表4.1.1相同的规模列出数据: 时, 依次为168、1229、9592、78498、664579; 约为144.765、1085.736、8685.890、72382.414、620420.688;使用未过早取整的分母,比值约为1.161、1.132、1.104、1.084、1.071。该近似描述大规模分布,不是判断某一个整数是否素数的充要条件。
定理4.1.4及推论4.1.2:合数 必有不超过 的真因子,进一步必有不超过 的素因子。因为若 且 ,二者不能都大于平方根;若较小因子仍为合数,再取其素因子即可。因此试除时只需检查不超过平方根的素数。
【例4.1.2】判断127、133是否为素数。
解:两数的平方根都小于13,只需试除2、3、5、7、11。127均不被这些素数整除,因此是素数;133被7整除,,因此是合数。发现一个真因子即可停止判合数,不需要继续把所有因子找完。
埃拉托色尼筛法:先排除1,从2起依次选未被删去的数 ,保留 为素数并删除其更大倍数。实现时可从 开始删,因为更小的倍数已被更小素因子处理。处理完 后,所有未被删除且大于1的数恰为不超过 的素数。
100以内素数为2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。可以用这些素数继续筛到 ,同一原则推广到更大上界。
形如 的素数称梅森素数。若指数 为合数且 ,则 ,故不可能为素数;指数为素数却不保证结果素,例如 ,而指数2、3、5、7分别产生3、7、31、127。教材记录的2024年发现是 ,该记录应理解为教材所记历史资料,不是未经核实宣称的当前纪录。素性测试与把合数完全分解是不同任务;教材还介绍了2004年AKS确定性多项式时间素性测试的结果。
