数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 1135|回复: 5

证明2^n+1被费马素数的筛选掉关系为1/2^K

[复制链接]
发表于 2019-2-13 16:58 | 显示全部楼层 |阅读模式
数列是2^n+1,n取正整数;费马素数是2^2^m+1,这里的k=(m+1),当m=0时,费马素数是3(第一个费马素数),它能淘汰掉1/2^1的合数,即数列中有50%的数是3的倍数,换句话说,每隔一个数就有素数3的因子(在2^n+1数列中),这里k=(0+1)=1;当m=1时,费马素数是5(第二个费马素数),它能淘汰掉1/2^2的合数,即数列中有25%的数是5的倍数,换句话说,每隔3个数就有素数5的因子(在2^n+1数列中),这里k=(1+1)=2;当m=2时,费马素数是17(第三个费马素数),它能淘汰掉1/2^3的合数,即数列中有12.5%的数是17的倍数,换句话说,每隔7个数就有素数17的因子(在2^n+1数列中),这里k=(2+1)=3;当m=3时,费马素数是257(第四个费马素数),它能淘汰掉1/2^4的合数,即数列中有6.25%的数是257的倍数,换句话说,每隔15个数就有素数257的因子(在2^n+1数列中),这里k=(3+1)=4;当m=4时,费马素数是65537(第五个费马素数),它能淘汰掉1/2^5的合数,即数列中有3.125%的数是65537的倍数,换句话说,每隔31个数就有素数65537的因子(在2^n+1数列中),这里k=(4+1)=5;到目前为止仅知道这5个费马素数,而且数列中的合数只能含一种费马素数,即它们淘汰掉的合数不发生交叉现象,所以这5个费马素数共能筛除掉(1/2+1/4+1/8+1/16+1/32)=31/32的合数,最多有1/32的项有可能是素数,实际上在上述数列中只有费马数有可能是素数,其余的都是合数。
 楼主| 发表于 2019-2-14 09:53 | 显示全部楼层
先分析一下2^n+1模2^2^k+1形的数,前边是数列2的幂+1的数,模是
费马数,有数列2^n-2模2^k+1形的数可知,它的剩余类个数为2k;
那么,2^n+1模2^2^k+1是不是也是2*2^k个剩余类呢?答案是肯定的,
数列2^n+1,对于每一个确定n来说,我们都可以表示成m*2^(k+1)+i
的形式,现在把任意的第n项写成2+1+2+4+8+……+2^(n-1)形式,它
有n+1项的和,在等比数列中多一个2,我们把2单独分开,即它不在
记项数之内,我们说数列的第n项写成等比数列和的多项式形式时,
展开式含有n项(另外跨着一个2),这时我们把2^(k+1)项分成一段,
那么,最多剩下2^(k+1)-1项,连n是它整倍数时,最多有2^(k+1)种余项,
那每段中的项组合后是不是都能整除2^2^k+1呢?能。2^(k+1)项正好
是2^k的2倍,每两项一组,正好分成2^k组,分组时,2项的间隔正好
隔2^k项,每两项提出它们的公共因子2^d,剩下的因数正好是2^2^k与1,
即每组都可以整除2^2^k+1,所以余数就是所剩项的和,安2^(k+1)划分
段,最多剩余2^(k+1)-1项,当正好划分成整段时,余数为2,此时一项也没
有留下,所以共有2^(k+1)个剩余类,当剩余2^k项时,整除2^2^k+1。
所以费马数无论是不是素数,它都筛选掉1/2^(k+1)比例的合数,
从第一个费马素数3开始,1/2,1/4,1/8,……,1/2^(K+1),它们的和为
(2^(k+1)-1)/2^(K+1),即前m个费马数可以筛选掉(2^(k+1)-1)/2^(K+1)
只剩下1/2^(K+1)可能是素数,即只有费马数可能是素数。
通过数列2^n+1模2^2^K+1剩余类个数的证明,可知,每个费马数因数
都出现在剩余类个数一半的位置上,每个费马数的剩余类个数周期是
2*2^K,所以费马数因数出现在h*2*2^K+2^K位置上。费马数3,k=0,
所以,它出现在2h+1的位置(h可以为0),即出现在奇数项上,1,3,5,
……,2h+1;费马数5,k=1,所以出现位置是4h+2(h可以取0,一切的
费马数因子的出现位置公式中的h都可以取0),2,6,10,14,……,4h+2
费马数17,k=2,所以出现位置是8h+4,即4,12,20,28,……,8h+4;
费马数257,k=3,所以出现位置是,16h+8,即8,24,40,……,16h+8;
费马数65537,k=4,所以出现位置是,32h+16,即16,48,80,……,32h+16;
不在赘述,这前5个是费马素数,后边的至今没有人再找到费马素数,
但是在2^n+1的数列中,费马数因子的出现位置与是否为素数无关,
它们的等差数列的并集正好是自然数集,即全部覆盖,每个费马数
因子的出现位置与另一个费马数因子的出现位置不交叉,即数列中
的任何一项只能含有一种费马数因子。
 楼主| 发表于 2019-2-18 14:48 | 显示全部楼层
无论费马素数还是费马伪素它们都是其他2^n+1的因子,而且每个费马数都筛掉1/2^(K+1)的合数(在数列2^n+1中),任何费马数都互质,所以,要想是费马伪素,必须是费马数,而(4^p - 1)/3 并不是它的表现形式,即无法写成2^2^n+1的形式,所以它不是费马数,更不是费马伪素,还有一个重要问题,那就是素数3是费马素数,如果(4^p - 1)/3是一个整数,也就是说,如果它含素数因子3,那它一定不是费马数,就谈不到费马伪素了,因为一个2^n+1这样形式的合数,它只能含有一种费马数,不能含有2种费马数。
(4^p - 1)/3分解为(2^p+1)*(2^p-1)/3,    在2^p+1合数中有好多素数因子不含有,2^p-1中如果不是素数p,是正整数n的情况下,除不含素数2以外,含有所有素数因子,现在规定的是素数,所以它含有的素数因子也不全,而且任何p不能写成2^K的形式,所以2^p+1不是费马数,2^p-1也不是费马数(实际上无需分解,它们的积不能表示成费马数,因子更不能表示),所以费马伪素就不存在。
 楼主| 发表于 2019-2-18 14:58 | 显示全部楼层
上楼最后一句是说,(4^p - 1)/3 形式的费马伪素不存在,即它不含有费马数因子(一个除3就把它给推翻了,因为3是费马素数,任何合数不含有两种以上费马素数)。
 楼主| 发表于 2019-2-18 15:30 | 显示全部楼层
数列2^n+1与数列2^n-1正好交叉出现素数3的因子,所以(2^2P-1)/3一定是正整数。
 楼主| 发表于 2019-2-18 18:27 | 显示全部楼层
定义
编辑
其定义是:对自然数和一个与其互素的自然数a,如果  整除a- 1,则称  是一个以a为底的费马伪素数或者关于a的费马伪素数。最小的费马伪素数是341(=11×31,关于2)。如果  关于任何与其互素的数都是费马伪素数,则称  是绝对伪素数(或卡迈克尔数,来自找到第一个绝对伪素数的数学家罗伯特·丹尼·卡迈克尔)。最小的绝对伪素数是561。
有人已经证明了费马伪素数的个数是无穷的。有一位数学家如此评论:“对于素数,费马小定理肯定是正确的;但他没说在合数中就不正确。”事实上,费马小定理给出的是关于素数判定的必要非充分条件。
另外,若:  不是素数(如下表中的情况),则它就一定是伪素数。 这些当中包含了所有的费马合数(当n=2),梅森合数(当n=p)及瓦格斯塔夫合数(当n=2p) [1]  
这是从百度百科搜集出来的费马伪素数的定义,你的情况和瓦格斯塔夫合数(当n=2p) 有区别吗?或许有些区别,有个除3,还有个是除3前是合数。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 09:40 , Processed in 0.058594 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表