|
|

楼主 |
发表于 2016-1-13 09:32
|
显示全部楼层
本帖最后由 xingjw 于 2016-1-13 10:19 编辑
素数有很多神奇的性质:
1. 素数的个数无限多(不存在最大的素数)
证明:反证法,假设存在最大的素数P,那么我们可以构造一个新的数2 * 3 * 5 * 7 * … * P + 1(所有的素数乘起来加1)。显然这个数不能被任一素数整除(所有素数除它都余1),这说明我们找到了一个更大的素数。
2. 存在任意长的一段连续数,其中的所有数都是合数(相邻素数之间的间隔任意大)
证明:当0<a<=n时,n!+a能被a整除。长度为n-1的数列n!+2, n!+3, n!+4, …, n!+n中,所有的数都是合数。这个结论对所有大于1的整数n都成立,而n可以取到任意大。
3. 所有大于2的素数都可以唯一地表示成两个平方数之差。
证明:大于2的素数都是奇数。假设这个数是2n+1。由于(n+1)^2=n^2+2n+1,(n+1)^2和n^2就是我们要找的两个平方数。下面证明这个方案是唯一的。如果素数p能表示成a^2-b^2,则p=a^2-b^2=(a+b)(a-b)。由于p是素数,那么只可能a+b=p且a-b=1,这给出了a和b的唯一解。
4. 当n为大于2的整数时,2^n+1和2^n-1两个数中,如果其中一个数是素数,那么另一个数一定是合数。
证明:2^n不能被3整除。如果它被3除余1,那么2^n-1就能被3整除;如果被3除余2,那么2^n+1就能被3整除。总之,2^n+1和2^n-1中至少有一个是合数。
5. 费马小定理, 如果p是素数,a是小于p的正整数,那么a^(p-1) mod p = 1。
证明:(a+1)^p-(a+1) = a^p + P(*)+1-a-1 = a^p – a (mod p), 其中P(*)为p的多项式。
6. 任意两个相邻的平方数之间,都存在不少于2个以上的素数。
|
|
|