20050424, 06:42  #1 
Aug 2004
Melbourne, Australia
2^{3}·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^((N1)/2) = 1 mod N. I expect that the converse is not true, (otherwise it would be very well known). But does anyone have a counterexample? I.e. Does anyone know a Proth prime P such that for all 1 < x < P we get x^((P1)/2) != 1 mod P ? The first few Proth numbers are 3,5,9,13,17,25,33,41,49,57,… Sloane's A080075 2^((31)/2) = 2 = 1 mod 3 2^((51)/2) = 4 = 1 mod 5 2^((131)/2) = 65 = 1 mod 13 ... 
20050424, 06:55  #2  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
x^((P1)/2) == 1 (mod P) iff x is a quadratic nonresidue modulo P, and there are always QNR modulo P for P>2, (P1)/2 of them to be specific. Alex Last fiddled with by akruppa on 20050424 at 06:56 Reason: typo 

20050424, 10:22  #3 
Aug 2004
Melbourne, Australia
2^{3}×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. 
20071127, 18:56  #4  
Oct 2007
63_{16} Posts 
.
Quote:
I am writing a program using Proth's theorem and don't want to try more than one x.. many thanks in advance. 

20071127, 20:02  #5  
Nov 2003
2^{2}·5·373 Posts 
Quote:
check is 2. 

20071127, 20:20  #6  
Oct 2007
63_{16} Posts 
.
Quote:
Edit: Or did you want to say that I compute x^((P1)/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 20071127 at 20:34 Reason: Wanted to add something 

20071128, 10:55  #7  
Nov 2003
16444_{8} Posts 
Quote:
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. 

20071128, 20:57  #8  
Oct 2007
3^{2}×11 Posts 
.
Quote:
It would be kind of you to mention other books. 

20071128, 21:13  #9 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Yes, the Legendre symbol (a/p) is 1 if a is a quadratic nonresidue modulo the prime p, 1 if a is a quadratic residue, and 0 if pa. 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 20071130 at 19:11 Reason: s/Jacobi/Legendre 
20071130, 18:35  #10 
Oct 2007
3^{2}×11 Posts 
.
I know how to compute the Legendre symbol, many thanks for your help.

20080130, 12:18  #11 
Oct 2007
99_{10} Posts 
.
It wasn't to difficult to program the check of the condition "(N/a) is a quadratic nonresidue". 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^((N1)/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 20080130 at 12:20 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Proth primes  ET_  Proth Prime Search  9  20201002 07:11 
Proth's Theorem  ATH  Math  9  20110215 19:09 
Proth theorem extended  Bill Bouris  Conjectures 'R Us  4  20090407 13:25 
Extended Proth Theorem  Cyclamen Persicum  Math  1  20040420 04:54 
Last possible proth tested!  Deamiter  PSearch  3  20030303 03:19 