mersenneforum.org Mp primality criterion?
 Register FAQ Search Today's Posts Mark Forums Read

 2012-04-26, 07:46 #1 jnml   Feb 2012 Prague, Czech Republ 132 Posts Mp primality criterion? For all prime p, Mp is prime iff -3 is a quadratic residue modulo Mp.I'm not able to prove the above nor I'm able to disprove it (e.g. by finding a counter example). It might be a diferent/derived form of something already known (and thus possibly known to be false). Then again, I failed to find that. Thanks in advance for any comments. Enlightening me will be appreciated ;-) (My first post ever on mersenneforum.org. I'm a programmer.)
2012-04-26, 08:20   #2
davieddy

"Lucan"
Dec 2006
England

145128 Posts

Quote:
 Originally Posted by jnml For all prime p, Mp is prime iff -3 is a quadratic residue modulo Mp.I'm not able to prove the above nor I'm able to disprove it (e.g. by finding a counter example). It might be a diferent/derived form of something already known (and thus possibly known to be false). Then again, I failed to find that. Thanks in advance for any comments. Enlightening me will be appreciated ;-) (My first post ever on mersenneforum.org. I'm a programmer.)
Welcome aboard.
Just hope someone reads this before Silverman does.

David

David

 2012-04-26, 10:51 #3 kar_bon     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.
 2012-04-26, 12:05 #4 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts First counterexample is p=37, where -3 is a QR modulo both prime factors 223 and 616318177.
2012-04-26, 12:17   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by akruppa First counterexample is p=37, where -3 is a QR modulo both prime factors 223 and 616318177.
is 2^37-1 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 2012-04-26 at 12:19

 2012-04-26, 12:17 #6 akruppa     "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 2012-04-26 at 12:21
2012-04-26, 12:24   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 is 2^37-1 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.
doh I realized the key word is "is" not "can".

Last fiddled with by science_man_88 on 2012-04-26 at 12:24

2012-04-26, 12:58   #8
alpertron

Aug 2002
Buenos Aires, Argentina

32·149 Posts

Quote:
 Originally Posted by akruppa First counterexample is p=37, where -3 is a QR modulo both prime factors 223 and 616318177.
With this information it can be easily found that:
105712246062 = -3 (mod 237 - 1)
146978206512 = -3 (mod 237 - 1)
1227411328202 = -3 (mod 237 - 1)
1268677288652 = -3 (mod 237 - 1)

Using the Jacobi symbol one can find that when the exponent p is prime, -3 is a quadratic residue mod 2p-1.

More solutions for exponents less than 200:

103712505979911189142 = -3 (mod 267 - 1)
111566182298544279092 = -3 (mod 267 - 1)
1364173343598219850182 = -3 (mod 267 - 1)
1372027019916852940132 = -3 (mod 267 - 1)

11058467599973161044841295230972 = -3 (mod 2101 - 1)
11517000996404213229942402047942 = -3 (mod 2101 - 1)
13836011008160374799991662059572 = -3 (mod 2101 - 1)
14294544404591426985092768876542 = -3 (mod 2101 - 1)

11762899295420233078804271262322 = -3 (mod 2103 - 1)
21267947635838653175803766333502 = -3 (mod 2103 - 1)
80144100382419698943932490096572 = -3 (mod 2103 - 1)
89649148722838119040931985167752 = -3 (mod 2103 - 1)

976840220350867178541112131000359526935452 = -3 (mod 2139 - 1)
1537366813380174913535310573099903279710322 = -3 (mod 2139 - 1)
5431616061160644818194601387102709690908552 = -3 (mod 2139 - 1)
5992142654189952553188799829202253443683422 = -3 (mod 2139 - 1)

Last fiddled with by alpertron on 2012-04-26 at 13:40

2012-04-26, 13:48   #9
jnml

Feb 2012
Prague, Czech Republ

132 Posts

Quote:
 Originally Posted by akruppa 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.
Thanks! Indeed p=37 is an counter example.

$x^2 \equiv -3 \ (\text{mod M}p)$,
(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:
 Moved to Misc. Math.
Rightfully IMHO ;-)

Quote:
 Originally Posted by alpertron With this information it can be easily found that: 105712246062 = -3 (mod 237 - 1) 146978206512 = -3 (mod 237 - 1) 1227411328202 = -3 (mod 237 - 1) 1268677288652 = -3 (mod 237 - 1) Using the Jacobi symbol one can find that when the exponent p is prime, -3 is a quadratic residue mod 2p-1.
Here I'm lost as for e.g. p=11 I'm failing to verify (and/or understand) that (Mathematica session):

$p=11; \ \text{Reduce}[x{}^{\wedge}2==-3, \ x, \ \text{Modulus}\to 2{}^{\wedge}p-1] \\

\text{False}
$

The same works in this case:

$
p=37; \ \text{Reduce}[x{}^{\wedge}2==-3,\ x,\ \text{Modulus}\to 2{}^{\wedge}p-1] \\

x==10571224606 \ \|\ x==14697820651 \ \| \ x==122741132820 \ \| \ x==126867728865
$

or

$
p=13; \ \text{Reduce}[x{}^{\wedge}2==-3, \ x, \ \text{Modulus}\to 2{}^{\wedge}p-1] \\

x==181 \ \| \ x==8010
$

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 2p-1." or show such x for p=11?

In any case, thanks a lot to all commentators for valuable help/insights!

2012-04-26, 13:53   #10
alpertron

Aug 2002
Buenos Aires, Argentina

32·149 Posts

Quote:
 Originally Posted by jnml Can you please clarify/explain "when the exponent p is prime, -3 is a quadratic residue mod 2p-1." or show such x for p=11?
Sorry, I meant that when 2p-1 is prime, -3 is a quadratic residue mod that number.

2012-04-26, 13:55   #11
jnml

Feb 2012
Prague, Czech Republ

2518 Posts

Quote:
 Originally Posted by alpertron Sorry, I meant that when 2p-1 is prime, -3 is a quadratic residue mod that number.
Thanks, now it's clear to me ;-)

 Similar Threads Thread Thread Starter Forum Replies Last Post Mini-Geek Math 8 2009-09-24 21:18 marco_calabresi Information & Answers 3 2009-04-17 19:44 maxal Math 23 2008-03-09 21:09 Unregistered Homework Help 4 2007-07-18 08:36 Citrix Math 3 2005-09-19 15:06

All times are UTC. The time now is 23:57.

Wed Jan 20 23:57:48 UTC 2021 up 48 days, 20:09, 0 users, load averages: 1.14, 1.46, 1.55