Question

一道较难的数论题，大神帮帮忙

设n>2,且对于满足0<=k<=根号下(n/3)的每一个整数k，数k^2+k+n都是素数，试证对于满足0<=k<=n-2的每个整数k，数k^2+k+n也都是素数

Answer 1

假设结论不成立，设m是使得k^2+k+n是合数的最小正整数，则m>√(n/3)。
则对于0<=k<=m-1，k^2+k+n都是素数。
设m^2+m+n=p*q，其中p是最小素因子。则q>=p（q不一定是素数）。
首先，p<n，因为p<√(m^2+m+n)<=√((n-2)^2+n-2+n)=√(n^2-2n+2)<n.
所以p与k^2+k+n(k=0...m-1)这m个素数互不相同。
其次，p>=2m+1.
因为对于k^2+k+n(k=-m,-m+1......m-1)这2m个数，它们都是与p不相等的素数，
所以对于k^2+k+n，当k=-m,-m+1......m-1时mod p不余0，而当k=-m-1或m时mod p余0。
k^2+k+n mod p具有周期p，而根据上述事实(对于相邻整数k，k^2+k+n mod p是否余0)
我们发现周期至少为2m+1，
也即p>=2m+1.
所以m^2+m+n=p*q>=p^2>=4m^2+4m+1.
所以3m^2+3m<=n-1.
但当m>√(n/3)时，左边>n，矛盾。
因此假设不成立，原命题成立。
(PS: 根据上述论证发现可将√(n/3)优化为3m^2+3m=n-1的根，即√(n/3-1/12)-1/2.)