还是不会的两道题

石崇的BOSS

没听懂，我知道大概是用反证法，但是后面那个怎么就矛盾了？请详细说一下……

superacid

假如只有有限个，那你找一个和他们都互质的，就把前面的都乘起来就可以了

石崇的BOSS

乘起来是它的因子吗？

lulijie

任意一个数N，设x为N以内的所有素数的积。
那么x^2＋x+1必为素数。
    （需要证明！）
取y等于1，那么p＝x^2＋x+1 显然符合题意。
所以p有无穷多个。

Paracel_007

原帖由 chuchudengren 于 2010-7-7 14:36 发表

用二次互反律应该可以得到3k+1形的素数都满足，这样的是不是有无穷多我就不知道了，似乎没有3k-1有无穷多好证

貌似有个什么定理说任何ax+b都有无穷多个素数

lulijie

x^2＋x+1必为素数，是错的。
但只要一定的比例是素数，照样可以证明本题。

Paracel_007

原帖由 lulijie 于 2010-7-7 18:33 发表
任意一个数N，设x为N以内的所有素数的积。
那么x^2＋x+1必为素数。
    （需要证明！）

这个恐怕不是这样吧
x=p₁p₂...p_n
M=x²+x+1
显然p_i不能整除M，因为p_i整除M-1，（M-1,M）=1
所以M有不同于p₁,p₂...p_n的素因子
有点像素数有无穷个的证明

[ 本帖最后由 Paracel_007 于 2010-7-7 18:41 编辑 ]

chuchudengren

原帖由 Paracel_007 于 2010-7-7 18:40 发表 这个恐怕不是这样吧x=p1p2...pnM=x2+x+1显然pi不能整除M，因为pi整除M-1，（M-1,M）=1所以M有不同于p1,p2...pn的素因子有点像素数有无穷个的证明

x2+x+1<(x+1)2， 因此有小于x+1的素因子。

lulijie

假设  x^2＋x+1 形式的素数只有有限个。那么设最大的x取M。
即假设当x>M时，所有的x^2＋x+1都是合数。
那么x^2＋x+1的素因子中必有一个最大的，设为s。
（若x^2＋x+1的素因子中没有最大的，那么，显然证明了楼主的题目，p有无穷个）
x<M以内的 x^2＋x+1，必有一个最大的素因子，设为t，取s和t中的较大的数记做r。
那么取x等于r以内的所有素数的乘积，x^2＋x+1 必为素数，和我们的假设矛盾。

[ 本帖最后由 lulijie 于 2010-7-7 18:58 编辑 ]

lulijie

现在重新把证明过程总结如下：
－－－－－－－－－－－－－－－－－－－－－－－
对于任意的x，x^2+x+1 都可以写成p*q   的形式
     其中p是x^2+x+1的最大素因子。（若x^2+x+1是素数，那么q等于1）
假设对于任意的x，p的最大取值是M。
那么取x等于M以内的所有素数的乘积，这时x^2+x+1显然不能被M以内的所有素数整除，
所以此时x^2+x+1的p值必定大于M，与我们的假设矛盾。
所以对于任意的x，p的最大取值不存在，所以必有无穷多个p。