。至今只发现27个,即Р是否有无穷个梅森素数还未证明。不是素数。Р3.费马素数形如Р(为自然数)Р的整数为素数者称为费马(Fermat)素数。至今只发现5个费马素数Р尽管如此,迄今为止仍然没有发现素数的模型或产生素数的有效公式,因而寻找大的素数必须借助计算机一个一个地找。用计算机算两个512位(二进制)的素数的乘积是一件很容易的事情,但是如果给定一个Р1024位的数,让你找出它是哪两个素数的乘积就困难多了,数学家至今还没有找到一种有效的方法去迅速分解一个合数。关于大合数因子分解的时间复杂度下限目前尚没有一般的结果,到现在为止的各种算法告诉人们这一时间下限将不低于,此结果明显比定理1给出的时间复杂度低。Р因为不是任意两个整数都具有整除关系,所以我们引进带余数除法或欧几里得除法。Р定理7(欧几里得除法) 设是两个给定的整数,其中,则对任意的整数,存在惟一的整数,使得Р,。Р称为除的不完全商。Р在上式中取不同的,就得到不同形式的带余数除法。Р(1) 取,则,称为被除后的最小非负余数,此时,可以看出,的充要条件是;Р(2) 取,则,称为被除后的最小正余数,此时,可以看出,的充要条件是;Р(3) 取,则,称为被除后的最大非正余数,此时,可以看出,的充要条件是;Р(4) 取,则,称为被除后的最大负余数,此时,可以看出,Р的充要条件是;Р(5) 当为偶数时,取,有;取,有;Р当为奇数时,取,有Р这时,称为绝对值最小余数。Р例5 设,则对任意一个整数,Р被除后的最小非负余数为Р被除后的最小正余数为Р被除后的最大非正余数为Р被除后的最大负余数为Р被除后的绝对值最小余数为;Р被除后的最小非负余数为Р被除后的最小正余数为Р被除后的最大非正余数为Р被除后的最大负余数为Р被除后的绝对值最小余数为Р例6 证明:设是三个整数,则Р(1)对任意的整数,必有;Р(2)若,则;Р(3)若,则;Р(4)若,则。
全文预览
