资源描述：
《千万不要迷信规律——大反例合集》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、千万不要迷信规律：大反例合集 数学猜想并不总是对的，错误的数学猜想不占少数。关键在于，有时反例太大，找出反例实在是太困难了。这篇日志收集了很多“大反例”的例子，里面提到的规律看上去非常诱人，要试到相当大的数时才会出现第一个反例。千万不要迷信规律 圆上有n个点，两两之间连线后，最多可以把整个圆分成多少块？ 上图显示的就是n分别为2、3、4的情况。可以看到，圆分别被划分成了2块、4块、8块。规律似乎非常明显：圆周上每多一个点，划分出来的区域数就会翻一倍。 事实上真的是这样吗？让我们看看当n=5时
2、的情况： 果然不出所料，整个圆被分成了16块，区域数依旧满足2n-1的规律。此时，大家都会觉得证据已经充分，不必继续往下验证了吧。偏偏就在n=6时，意外出现了： 此时区域数只有31个。 最有名的素数生成公式 1772年，Euler曾经发现，当n是正整数时，n2+n+41似乎总是素数。事实上，n从1一直取到39，算出来的结果分别是：43,47,53,61,71,83,97,113,131,151,173,197,223,251,281,313,347,383,421,461,503,5
3、47,593,641,691,743,797,853,911,971,1033,1097,1163,1231,1301,1373,1447,1523,1601 这些数全都是素数。第一次例外发生在n=40的时候，此时402+40+41=402+40+40+1=(40+1)(40+1)=41×41。 xn-1的因式分解 x2-1分解因式后等于(x+1)(x-1)。x20-1分解因式后等于(x-1)(x+1)(x2+1)(x4-x3+x2-x+1)(x4+x3+x2+x+1)(x8-x6+x4-x2+1) 对于所
4、有的正整数n，xn-1因式分解后各项系数都只有可能是1或者-1吗？据说有人曾经算到了x100-1，均没有发现反例，终于放心大胆地做出了这个猜想。悲剧的是，这个猜想是错误的，第一个反例出现在n=105的情况，x105-1分解出来等于(x-1)(x2+x+1)(x4+x3+x2+x+1)(x6+x5+x4+x3+x2+x+1)(x8-x7+x5-x4+x3-x+1)(x12-x11+x9-x8+x6-x4+x3-x+1)(x24-x23+x19-x18+x17-x16+x14-x13+x12-x11+x10-x8+x7-x6+x5
5、-x+1)(x48+x47+x46-x43-x42-2x41-x40-x39+x36+x35+x34+x33+x32+x31-x28-x26-x24-x22-x20+x17+x16+x15+x14+x13+x12-x9-x8-2x7-x6-x5+x2+x+1) 以2为底的伪素数 下面是当n较小的时候，n与2n-2的值。 似乎有这样的规律：n能整除2n-2，当且仅当n是一个素数。如果真是这样的话，我们无疑有了一种超级高效的素数判定算法（2n可以用二分法速算，期间可以不断模n）。国外数学界一直传有“中国人
6、2000多年前就发现了这一规律”的说法，后来发现其实是对《九章算术》一书的错误翻译造成的。再后来人们发现，这个规律竟然是错误的。第一个反例是n=341，此时341能够整除2341-2，但341=11×31。 事实上，根据Fermat小定理，如果p是素数，那么p一定能整除2n-2。不过，它的逆定理却是不成立的，上面提到的341便是一例。我们把这种数叫做以2为底的伪素数。由于这种素数判定法的反例出人意料的少，我们完全可以用它来做一个概率型的素数判定算法。事实上，著名的Miller-Rabin素性测试算法就是用的这个原理。
7、Perrin伪素数 定义f(n)=f(n-2)+f(n-3)，其中f(1)=0，f(2)=2，f(3)=3。这个数列叫做Perrin数列。 似乎有这么一个规律：n能整除Perrin数列的第n项f(n)，当且仅当n是一个素数。如果这个规律成立的话，我们也将获得一个效率非常高的素数检验方法。根据MathWorld的描述，1899年Perrin本人曾经做过试验，随后Malo在1900年，Escot在1901年，以及Jarden在1966年都做过搜索，均未发现任何反例。直到1982年，Adams和Shanks才
8、发现第一个反例n=271441，它等于521×521，却也能整除f(271441)。下一个反例则发生在n=904631的时候，再下一个反例则是n=16532714。这种反例被称为Perrin伪素数。 最经典的大反例 说到大反例，这是我最喜欢举的例子。下面是大于1的正整
