20120426, 07:46  #1 
Feb 2012
Prague, Czech Republ
13^{2} Posts 
Mp primality criterion?
For all prime p, Mp is prime iff 3 is a quadratic residue modulo Mp.
(My first post ever on mersenneforum.org. I'm a programmer.) 
20120426, 08:20  #2  
"Lucan"
Dec 2006
England
14512_{8} Posts 
Quote:
But I'm afraid I can't help you. Just hope someone reads this before Silverman does. David David 

20120426, 10:51  #3 
Mar 2006
Germany
2×1,433 Posts 
can't resist
I don't know the answer, too, but I want to increase my postcount by one.

20120426, 12:05  #4 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
First counterexample is p=37, where 3 is a QR modulo both prime factors 223 and 616318177.

20120426, 12:17  #5 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
is 2^371 prime ? also he said is prime iff 3 is a quadratic residue mod Mp ,not, 3 is a quadratic residue mod Mp iff Mp is prime.
Last fiddled with by science_man_88 on 20120426 at 12:19 
20120426, 12:17  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
No, or it wouldn't have two prime factors.
Edit: he did say that, it's what "iff", a.k.a "if and only if" means. Moved to Misc. Math. Last fiddled with by akruppa on 20120426 at 12:21 
20120426, 12:24  #7 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
doh I realized the key word is "is" not "can".
Last fiddled with by science_man_88 on 20120426 at 12:24 
20120426, 12:58  #8  
Aug 2002
Buenos Aires, Argentina
3^{2}·149 Posts 
Quote:
10571224606^{2} = 3 (mod 2^{37}  1) 14697820651^{2} = 3 (mod 2^{37}  1) 122741132820^{2} = 3 (mod 2^{37}  1) 126867728865^{2} = 3 (mod 2^{37}  1) Using the Jacobi symbol one can find that when the exponent p is prime, 3 is a quadratic residue mod 2^{p}1. More solutions for exponents less than 200: 10371250597991118914^{2} = 3 (mod 2^{67}  1) 11156618229854427909^{2} = 3 (mod 2^{67}  1) 136417334359821985018^{2} = 3 (mod 2^{67}  1) 137202701991685294013^{2} = 3 (mod 2^{67}  1) 1105846759997316104484129523097^{2} = 3 (mod 2^{101}  1) 1151700099640421322994240204794^{2} = 3 (mod 2^{101}  1) 1383601100816037479999166205957^{2} = 3 (mod 2^{101}  1) 1429454440459142698509276887654^{2} = 3 (mod 2^{101}  1) 1176289929542023307880427126232^{2} = 3 (mod 2^{103}  1) 2126794763583865317580376633350^{2} = 3 (mod 2^{103}  1) 8014410038241969894393249009657^{2} = 3 (mod 2^{103}  1) 8964914872283811904093198516775^{2} = 3 (mod 2^{103}  1) 97684022035086717854111213100035952693545^{2} = 3 (mod 2^{139}  1) 153736681338017491353531057309990327971032^{2} = 3 (mod 2^{139}  1) 543161606116064481819460138710270969090855^{2} = 3 (mod 2^{139}  1) 599214265418995255318879982920225344368342^{2} = 3 (mod 2^{139}  1) Last fiddled with by alpertron on 20120426 at 13:40 

20120426, 13:48  #9  
Feb 2012
Prague, Czech Republ
13^{2} Posts 
Quote:
, (1.) has for p=37 solutions: +/10571224606 and +/14697820651 (thanks alpertron) and disproves the OP. Revised (aka attempt to salvage the initial observation ;) version[s]: a) For all prime p, Mp is prime iff (1.) has exactly 2 solutions. (?) b) For all prime p, if 3 is a QNR modulo Mp then Mp is composite. (?) ad a) In other words, if Mp is composite, 3 will either not be a quadratic residue modulo Mp (ex. p=11, 23, 41, 43, 47, ...), or there will be more than 2 solutions to (1.), like is the case of p=37, 67, 101... (Note: Assuming, if any, there is an even number of solutions to (1.) in pairs of opposite sign. For p=2 the solutions 0 and 0 are here considered a "pair" too.) Quote:
Quote:
The same works in this case: or Just to be sure, I've done an exhaustive search for p=11 and if I've hacked the code correctly, there is no x in [0,M11) such that x^2 === 3 (mod M11). Can you please clarify/explain "when the exponent p is prime, 3 is a quadratic residue mod 2^{p}1." or show such x for p=11? In any case, thanks a lot to all commentators for valuable help/insights! 

20120426, 13:53  #10 
Aug 2002
Buenos Aires, Argentina
3^{2}·149 Posts 

20120426, 13:55  #11 
Feb 2012
Prague, Czech Republ
251_{8} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
primality of F33  MiniGeek  Math  8  20090924 21:18 
Primality searches and primality successes  marco_calabresi  Information & Answers  3  20090417 19:44 
primality of ((p+1)^p1)/p^2  maxal  Math  23  20080309 21:09 
Primality  Unregistered  Homework Help  4  20070718 08:36 
N1 primality test  Citrix  Math  3  20050919 15:06 