证明2^n+1被费马素数的淘汰关系为1/2^K
数列是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的项有可能是素数，实际上在上述数列中只有费马数有可能是素数，其余的都是合数。 先分析一下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的数列中，费马数因子的出现位置与是否为素数无关，
它们的等差数列的并集正好是自然数集，即全部覆盖，每个费马数
因子的出现位置与另一个费马数因子的出现位置不交叉，即数列中
的任何一项只能含有一种费马数因子。
页:
[1]