High first prime mod-root Quadratics

[grandpascorpion]

Find a quadratic equation f(x)=ax^2+bx+c

with the maximum first prime p such that there exists some f(x)= 0 (mod p)

========================================

For instance, for f(x)=x^2+x+41, the first such prime is 41 (f(0) = 0 (mod 41)). There are no earlier primes with a solution.

I found (really bumped into) one quadratic such that the first prime is 127. Can anyone improve on this and advise on the method they used for finding the polynomial?

[Citrix]

a*x^2+b*x+c, where a,b are any integer and c=M(43)

Then f(0)=M(43) is prime!

This will be the largest known function.

Citrix

[grandpascorpion]

Here's a counterexample to your claim:

Say we have f(x)=x^2 + M (where M is a mersenne prime or generally any number 2^n-1)

For p=2, x=1 is a solution for this polynomial: 1 + (2^p-1) = 0 (mod 2)

==========================================

Further explanation:
For the x^2+x+41 example, there are no cases where f(x)=0 (mod p) where 2<= p <= 40.

41 is the first prime number where you have a zero.

There's another polynomial where the 127 is the first prime number

[grandpascorpion]

THIS:

For p=2, x=1 is a solution for this polynomial: 1 + (2^p-1) = 0 (mod 2)

SHOULD READ:

For p=2, x=1 is a solution for this polynomial: 1 + (2^n-1) = 0 (mod 2)

[akruppa]

A polynomial of degree at most 3 is irreducible iff it has no linear factor, i.e. a root. It should be possible to determine irreducible quadratics in GF(2), GF(3), GF(5), ..., and combine the coefficients via the CRT. The coefficients will become huge, though.

Alex

[akruppa]

For example, x^2+x+2812387941219215279581047800530146873108208571981 should have no roots in GF(p) for 2<=p<=127. Created with this Pari/GP line:

r=Mod(1,2);forprime(p=3,127,i=1;while(polisirreducible(Mod(1,p)*x^2+Mod(1,p)*x+Mod(i,p))==0,i++);r=chinese(r,Mod(i,p)));r

I don't know how to make solutions with small coefficients.

Alex

[grandpascorpion]

Thanks for that insight Alex.

[grandpascorpion]

Sorry for the naive question, but since we know that
x^2+x+41 is prime for 0 <= n < 41, how can we use that value to knock down the constant term in the polynomial above?

For instance, the value at 37 is Mod[4363874813651,742073813810].
could 4363874813651 be replaced by 41?

*** EDIT: I see that doesn't work.

[akruppa]

Not a naive question at all. I suppose it should still produce a polynomial with no roots mod small primes. Starting with r=41 (mod 37#), then adding coefficient mod p, 41<=p<=limit by the CRT. However it probably won't make the coefficient any smaller. During the CRT reconstruction, modular inverses of the separate residues are computed and the inverses aren't necessarily small because the residues were. I.e.

? chinese(Mod(2,101), Mod(3,103))
%1 = Mod(5153, 10403)

Alex

[grandpascorpion]

I found (really bumped into) one quadratic such that the first prime is 127

BTW, the polynomial is : x^2 - 99999x + 1116427201
(from http://www.shyamsundergupta.com/canyoufind.htm [found by Brian Trial when looking for polynomials that produce the most primes for X = 1 to 100,000])