mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2012-04-26, 07:46   #1
jnml
 
Feb 2012
Prague, Czech Republ

132 Posts
Default 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.)
jnml is offline   Reply With Quote
Old 2012-04-26, 08:20   #2
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

145128 Posts
Default

Quote:
Originally Posted by jnml View Post
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.
But I'm afraid I can't help you.
Just hope someone reads this before Silverman does.

David

David
davieddy is offline   Reply With Quote
Old 2012-04-26, 10:51   #3
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×1,433 Posts
Default can't resist

I don't know the answer, too, but I want to increase my postcount by one.
kar_bon is offline   Reply With Quote
Old 2012-04-26, 12:05   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

First counterexample is p=37, where -3 is a QR modulo both prime factors 223 and 616318177.
akruppa is offline   Reply With Quote
Old 2012-04-26, 12:17   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-04-26, 12:17   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2012-04-26, 12:24   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-04-26, 12:58   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32·149 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
alpertron is offline   Reply With Quote
Old 2012-04-26, 13:48   #9
jnml
 
Feb 2012
Prague, Czech Republ

132 Posts
Default

Quote:
Originally Posted by akruppa View Post
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 View Post
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] \\<br />
<br />
\text{False}<br />

The same works in this case:

<br />
p=37; \ \text{Reduce}[x{}^{\wedge}2==-3,\ x,\ \text{Modulus}\to 2{}^{\wedge}p-1] \\<br />
<br />
x==10571224606 \ \|\ x==14697820651 \ \| \ x==122741132820 \ \| \ x==126867728865<br />

or

<br />
p=13; \ \text{Reduce}[x{}^{\wedge}2==-3, \ x, \ \text{Modulus}\to 2{}^{\wedge}p-1] \\<br />
<br />
x==181 \ \| \ x==8010<br />

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!
jnml is offline   Reply With Quote
Old 2012-04-26, 13:53   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32·149 Posts
Default

Quote:
Originally Posted by jnml View Post
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.
alpertron is offline   Reply With Quote
Old 2012-04-26, 13:55   #11
jnml
 
Feb 2012
Prague, Czech Republ

2518 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
primality of F33 Mini-Geek Math 8 2009-09-24 21:18
Primality searches and primality successes marco_calabresi Information & Answers 3 2009-04-17 19:44
primality of ((p+1)^p-1)/p^2 maxal Math 23 2008-03-09 21:09
Primality Unregistered Homework Help 4 2007-07-18 08:36
N-1 primality test 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.