mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2005-09-23, 15:59   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default 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
grandpascorpion is offline   Reply With Quote
Old 2005-09-23, 18:04   #2
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-09-23, 18:23   #3
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default 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
grandpascorpion is offline   Reply With Quote
Old 2005-09-23, 18:35   #4
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default 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)
grandpascorpion is offline   Reply With Quote
Old 2005-09-23, 19:15   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A016 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-09-23, 19:43   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-09-23, 19:51   #7
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1F716 Posts
Default

Thanks for that insight Alex.
grandpascorpion is offline   Reply With Quote
Old 2005-09-23, 21:02   #8
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1F716 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2005-09-23, 21:15   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000002 Posts
Default

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#
akruppa is offline   Reply With Quote
Old 2005-09-25, 13:45   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Root Systems and my prime equation alienearcandyeb Miscellaneous Math 7 2010-08-09 18:17
A high-performance degree-6 root sieve jasonp Msieve 20 2010-06-11 22:40
square root modulo prime Raman Math 1 2010-02-16 21:25
Cube root mfgoode Homework Help 10 2007-10-05 04:12
Running Prime on High Performance Computer Clustering 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.