mersenneforum.org > Math Converse of Proth's Theorem
 Register FAQ Search Today's Posts Mark Forums Read

 2005-04-24, 06:42 #1 Dougy     Aug 2004 Melbourne, Australia 23·19 Posts Converse of Proth's Theorem Let N=k.2^n+1 for some k < 2^n. (a Proth number) Proth's Theorem states: N is prime if there exists a natural number x such that x^((N-1)/2) = -1 mod N. I expect that the converse is not true, (otherwise it would be very well known). But does anyone have a counter-example? I.e. Does anyone know a Proth prime P such that for all 1 < x < P we get x^((P-1)/2) != -1 mod P ? The first few Proth numbers are 3,5,9,13,17,25,33,41,49,57,… Sloane's A080075 2^((3-1)/2) = 2 = -1 mod 3 2^((5-1)/2) = 4 = -1 mod 5 2^((13-1)/2) = 65 = -1 mod 13 ...
2005-04-24, 06:55   #2
akruppa

"Nancy"
Aug 2002
Alexandria

246710 Posts

Quote:
 I.e. Does anyone know a Proth prime P such that for all 1 < x < P we get x^((P-1)/2) != -1 mod P ?
By Fermat's little theorem, x^(P-1) == 1 (mod P) for all primes P and integers x with gcd(x,P)=1. Taking square roots on both sides, we have x^((P-1)/2) == +-1 (mod P).

x^((P-1)/2) == -1 (mod P) iff x is a quadratic non-residue modulo P, and there are always QNR modulo P for P>2, (P-1)/2 of them to be specific.

Alex

Last fiddled with by akruppa on 2005-04-24 at 06:56 Reason: typo

 2005-04-24, 10:22 #3 Dougy     Aug 2004 Melbourne, Australia 23×19 Posts Hmmm... so it is an "if and only if" theorem then. I wonder why the "only if" is not included, (well at least not where I looked). Thanks Alex.
2007-11-27, 18:56   #4
Retep

Oct 2007

32·11 Posts
.

Quote:
 Originally Posted by akruppa By Fermat's little theorem, x^(P-1) == 1 (mod P) for all primes P and integers x with gcd(x,P)=1. Taking square roots on both sides, we have x^((P-1)/2) == +-1 (mod P). x^((P-1)/2) == -1 (mod P) iff x is a quadratic non-residue modulo P, and there are always QNR modulo P for P>2, (P-1)/2 of them to be specific. Alex
I am new to this, could anyone explain how one finds such a QNR or provide a link with more information?
I am writing a program using Proth's theorem and don't want to try more than one x.. many thanks in advance.

2007-11-27, 20:02   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Retep I am new to this, could anyone explain how one finds such a QNR or provide a link with more information? I am writing a program using Proth's theorem and don't want to try more than one x.. many thanks in advance.
One searches sequentially starting with 2,3,5,6,.... The expected number to
check is 2.

2007-11-27, 20:20   #6
Retep

Oct 2007

11000112 Posts
.

Quote:
 Originally Posted by R.D. Silverman One searches sequentially starting with 2,3,5,6,.... The expected number to check is 2.
How can I show that for example x = 2 is a QNR or not? (in the latter case I will then look at x = 3 ..)

Edit: Or did you want to say that I compute x^((P-1)/2) for x=2,3,..? I thought there is a way to find a suitable x immediately, like in Yves Gallot's Proth.exe.

Last fiddled with by Retep on 2007-11-27 at 20:34 Reason: Wanted to add something

2007-11-28, 10:55   #7
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by Retep How can I show that for example x = 2 is a QNR or not? (in the latter case I will then look at x = 3 ..) Edit: Or did you want to say that I compute x^((P-1)/2) for x=2,3,..? I thought there is a way to find a suitable x immediately, like in Yves Gallot's Proth.exe.
May I suggest reading a book on elementary number theory? I can recommend
some good ones.

What do you mean by "immediately"? (above). The internal details of
what proth.exe performs are not public....

You do not test for QNR by exponentiation. Use quad. reciprocity instead.
It is faster.

2007-11-28, 20:57   #8
Retep

Oct 2007

32·11 Posts
.

Quote:
 Originally Posted by R.D. Silverman May I suggest reading a book on elementary number theory? I can recommend some good ones. What do you mean by "immediately"? (above). The internal details of what proth.exe performs are not public.... You do not test for QNR by exponentiation. Use quad. reciprocity instead. It is faster.
Yves Gallot writes "A prime x for which N is a non-residue is selected by computing the Legendre symbol (N/x)." Does "N is a non-residue" mean (N/x) = -1? I only have a problem with the translation of "non-residue", because at the moment I only read a book about number theory in German.

It would be kind of you to mention other books.

 2007-11-28, 21:13 #9 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Yes, the Legendre symbol (a/p) is -1 if a is a quadratic non-residue modulo the prime p, 1 if a is a quadratic residue, and 0 if p|a. You can compute the Kronecker symbol (a generalization of the Legendre symbol) rather quickly with a recursive algorithm. A good description is in Crandall and Pomerance: Prime numbers. Alex Last fiddled with by akruppa on 2007-11-30 at 19:11 Reason: s/Jacobi/Legendre
 2007-11-30, 18:35 #10 Retep     Oct 2007 1438 Posts . I know how to compute the Legendre symbol, many thanks for your help.
 2008-01-30, 12:18 #11 Retep     Oct 2007 32·11 Posts . It wasn't to difficult to program the check of the condition "(N/a) is a quadratic non-residue". I want to know why this is enough, this means I'm looking for a proof of this "extended version" of Proth's theorem: a^((N-1)/2) = (N/a) = -1 (mod N) [a prime, N=k*2^n+1,k<2^n] which is a necessary and sufficient condition for N to be prime. Does anyone know where to find this proof? I have not found it in Crandall and Pomerance: Prime numbers. Last fiddled with by Retep on 2008-01-30 at 12:20

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ Proth Prime Search 14 2021-12-16 02:08 ATH Math 9 2011-02-15 19:09 Bill Bouris Conjectures 'R Us 4 2009-04-07 13:25 Cyclamen Persicum Math 1 2004-04-20 04:54 Deamiter PSearch 3 2003-03-03 03:19

All times are UTC. The time now is 21:53.

Tue May 17 21:53:06 UTC 2022 up 33 days, 19:54, 0 users, load averages: 1.82, 1.51, 1.46