|
伪素数，不明思议就是具有素数的某些重要性质，但又不是素数的数， 定义为满足费马小定理，但本身不是素数的数。 1636年，法国的一名律师，又号称'业余数学家之王'的费马，发现整数的一个性质，也是当今数论四大定理之一的——费马小定理。 费马 描述: 对于任意的素数p，和不是素数倍数的整数a，那么a ^ （p－1）-1 一定能被p整除。 这是一条非常漂亮的定理，意味着我们利用较小的数p和a，就可以构造指数增长的数，而且知道其整除性，这对大数的分解是很有用的。 比如我们计算2 ^ 2017除以13的余数，只需要分解2017=12*168+1，然后由费马小定理得知2^12除以13是余1的，那么262017=2^（12*168）*2 ， 立马得到我们要的结果是2。 后来莱布尼兹和欧拉都给出了证明，值得一提的是，欧拉推广了这个定理，不再把p限定为素数，而是推广成了欧拉函数ψ（x)。 欧拉 可是有个难题一直困扰着数学家，那就是费马小定理的逆命题是否成立？ 如果逆命题也成立，就意味着费马小定理将成为判断一个数是否是素数的重要，且十分有效的办法。 我们来看： 正命题：素数p一定满足费马小定理。（正是费马小定理的内容） 逆命题:满足费马小定理的一定是素数! 弱逆命题:不满足费马小定理的一定是合数! 很长一段时间里面，人们都相信逆命题是正确的，但是证明起来相当困难，1680~1681 年，莱布尼兹两次宣称证明了弱逆命题，但始终没有发表他的证明方法，该命题比逆命题稍弱，对于逆命题的证明终究没有进展。 直到1819年，法国数学家沙路斯发现了逆命题的一个反例，既a=2，p=341时满足费马小定理，但是341=11*31却是合数，这一发现让逆命题不攻而破，说明了费马小定理还不够强大！而且研究发现，这样的反例拥有无穷多个，这些反例统称为伪素数。 正整数分类 1950年，美国数学家发现一个偶伪素数161038，大家别以为这个数小容易找，这个数在费马小定理中是指数，所以寻找起来相当困难。 既然我们知道了伪素数有无穷多个，那么利用费马小定理去寻找素数的办法，就半路夭折了！ 另外伪素数远比素数少，比如前10亿自然数中，素数有50847534个，而伪素数只有5597个，大约占其万分之一。在1938年数学家普列特发明伪素数表，我们利用伪素数表就可以确定某个数是否是素数，比如一个数n，如果满足费马小定理，那么n一定是素数或者伪素数，只要和伪素数表一对比，那么就能确认n是素数还是伪素数了。 素数螺旋 后来素数学家们发现了很多判定伪素数的办法，也算是对素数研究开辟了另外一条路吧! |
|
|
