mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-04-24, 06:42   #1
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23·19 Posts
Question 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 ...
Dougy is offline   Reply With Quote
Old 2005-04-24, 06:55   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-04-24, 10:22   #3
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23×19 Posts
Default

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.
Dougy is offline   Reply With Quote
Old 2007-11-27, 18:56   #4
Retep
 
Retep's Avatar
 
Oct 2007

6316 Posts
Default .

Quote:
Originally Posted by akruppa View Post
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.
Retep is offline   Reply With Quote
Old 2007-11-27, 20:02   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Retep View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-11-27, 20:20   #6
Retep
 
Retep's Avatar
 
Oct 2007

6316 Posts
Default .

Quote:
Originally Posted by R.D. Silverman View Post
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
Retep is offline   Reply With Quote
Old 2007-11-28, 10:55   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by Retep View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-11-28, 20:57   #8
Retep
 
Retep's Avatar
 
Oct 2007

32×11 Posts
Default .

Quote:
Originally Posted by R.D. Silverman View Post
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.
Retep is offline   Reply With Quote
Old 2007-11-28, 21:13   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-11-30, 18:35   #10
Retep
 
Retep's Avatar
 
Oct 2007

32×11 Posts
Default .

I know how to compute the Legendre symbol, many thanks for your help.
Retep is offline   Reply With Quote
Old 2008-01-30, 12:18   #11
Retep
 
Retep's Avatar
 
Oct 2007

9910 Posts
Default .

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Proth primes ET_ Proth Prime Search 9 2020-10-02 07:11
Proth's Theorem ATH Math 9 2011-02-15 19:09
Proth theorem extended Bill Bouris Conjectures 'R Us 4 2009-04-07 13:25
Extended Proth Theorem Cyclamen Persicum Math 1 2004-04-20 04:54
Last possible proth tested! Deamiter PSearch 3 2003-03-03 03:19

All times are UTC. The time now is 01:52.

Thu Apr 22 01:52:22 UTC 2021 up 13 days, 20:33, 0 users, load averages: 2.34, 2.27, 2.27

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.