mersenneforum.org High first prime mod-root Quadratics
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-23, 15:59 #1 grandpascorpion     Jan 2005 Transdniestr 503 Posts High first prime mod-root 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 2005-09-23 at 16:02 Reason: clarity
 2005-09-23, 18:04 #2 Citrix     Jun 2003 32·52·7 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
 2005-09-23, 18:23 #3 grandpascorpion     Jan 2005 Transdniestr 1111101112 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^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 Last fiddled with by grandpascorpion on 2005-09-23 at 18:26
 2005-09-23, 18:35 #4 grandpascorpion     Jan 2005 Transdniestr 1111101112 Posts Correction: Fixing the ambiguity 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)
 2005-09-23, 19:15 #5 akruppa     "Nancy" Aug 2002 Alexandria 9A016 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 2005-09-23 at 19:16
 2005-09-23, 19:43 #6 akruppa     "Nancy" Aug 2002 Alexandria 25·7·11 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 I don't know how to make solutions with small coefficients. Alex
 2005-09-23, 19:51 #7 grandpascorpion     Jan 2005 Transdniestr 1F716 Posts Thanks for that insight Alex.
 2005-09-23, 21:02 #8 grandpascorpion     Jan 2005 Transdniestr 1F716 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 2005-09-23 at 21:14
 2005-09-23, 21:15 #9 akruppa     "Nancy" Aug 2002 Alexandria 1001101000002 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) Alex Last fiddled with by akruppa on 2005-09-23 at 21:19 Reason: 37#, not 41#
2005-09-25, 13:45   #10
grandpascorpion

Jan 2005
Transdniestr

503 Posts

Quote:
 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])

Last fiddled with by grandpascorpion on 2005-09-25 at 13:45

 Similar Threads Thread Thread Starter Forum Replies Last Post alienearcandyeb Miscellaneous Math 7 2010-08-09 18:17 jasonp Msieve 20 2010-06-11 22:40 Raman Math 1 2010-02-16 21:25 mfgoode Homework Help 10 2007-10-05 04:12 fxmulder Software 5 2003-11-20 22:42

All times are UTC. The time now is 13:19.

Tue Nov 24 13:19:49 UTC 2020 up 75 days, 10:30, 4 users, load averages: 1.35, 1.44, 1.64