20050923, 15:59  #1 
Jan 2005
Transdniestr
503 Posts 
High first prime modroot Quadratics
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? Last fiddled with by grandpascorpion on 20050923 at 16:02 Reason: clarity 
20050923, 18:04  #2 
Jun 2003
1,579 Posts 
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 
20050923, 18:23  #3 
Jan 2005
Transdniestr
503 Posts 
Maximum "first" prime
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^n1) For p=2, x=1 is a solution for this polynomial: 1 + (2^p1) = 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 Last fiddled with by grandpascorpion on 20050923 at 18:26 
20050923, 18:35  #4 
Jan 2005
Transdniestr
1F7_{16} Posts 
Correction: Fixing the ambiguity
THIS:
For p=2, x=1 is a solution for this polynomial: 1 + (2^p1) = 0 (mod 2) SHOULD READ: For p=2, x=1 is a solution for this polynomial: 1 + (2^n1) = 0 (mod 2) 
20050923, 19:15  #5 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
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 Last fiddled with by akruppa on 20050923 at 19:16 
20050923, 19:43  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
For example, x^2+x+2812387941219215279581047800530146873108208571981 should have no roots in GF(p) for 2<=p<=127. Created with this Pari/GP line:
Code:
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 Alex 
20050923, 19:51  #7 
Jan 2005
Transdniestr
503 Posts 
Thanks for that insight Alex.

20050923, 21:02  #8 
Jan 2005
Transdniestr
503 Posts 
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. Last fiddled with by grandpascorpion on 20050923 at 21:14 
20050923, 21:15  #9 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
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.
Code:
? chinese(Mod(2,101), Mod(3,103)) %1 = Mod(5153, 10403) Last fiddled with by akruppa on 20050923 at 21:19 Reason: 37#, not 41# 
20050925, 13:45  #10  
Jan 2005
Transdniestr
503 Posts 
Quote:
(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]) Last fiddled with by grandpascorpion on 20050925 at 13:45 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Root Systems and my prime equation  alienearcandyeb  Miscellaneous Math  7  20100809 18:17 
A highperformance degree6 root sieve  jasonp  Msieve  20  20100611 22:40 
square root modulo prime  Raman  Math  1  20100216 21:25 
Cube root  mfgoode  Homework Help  10  20071005 04:12 
Running Prime on High Performance Computer Clustering  fxmulder  Software  5  20031120 22:42 