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 ...

[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 ?
[/QUOTE]

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

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.

.
 

[quote=akruppa;53657]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[/quote]

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.

[QUOTE=Retep;119364]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.[/QUOTE]

One searches sequentially starting with 2,3,5,6,.... The expected number to
check is 2.

.
 

[quote=R.D. Silverman;119368]One searches sequentially starting with 2,3,5,6,.... The expected number to
check is 2.[/quote]

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.

[QUOTE=Retep;119371]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.[/QUOTE]

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.

.
 

[quote=R.D. Silverman;119421]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.[/quote]

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.

Yes, the Legendre symbol ([I]a[/I]/[I]p[/I]) is -1 if [I]a[/I] is a quadratic non-residue modulo the prime [I]p[/I], 1 if [I]a[/I] is a quadratic residue, and 0 if [I]p[/I]|[I]a[/I]. 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

.
 

I know how to compute the Legendre symbol, many thanks for your help.

.
 

It wasn't to difficult to program the check of the condition "([I]N[/I]/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.

[QUOTE=Retep;124330]It wasn't to difficult to program the check of the condition "([I]N[/I]/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.[/QUOTE]

You can find it in the Cunningham book. When k < 2^n, it means that
you know the factorization of N-1 up to sqrt(N). You can then use
theorems of Lehmer, Selfridge and Brillhart as described in the Cunningham
book.

.
 

[quote=R.D. Silverman;124336]You can find it in the Cunningham book. When k < 2^n, it means that
you know the factorization of N-1 up to sqrt(N). You can then use
theorems of Lehmer, Selfridge and Brillhart as described in the Cunningham
book.[/quote]

Could you tell me the title or ISBN of this book?
Many thanks in advance.

[quote=Retep;124343]Could you tell me the title or ISBN of this book?
Many thanks in advance.[/quote]

It is available online here:
[URL]http://www.ams.org/online_bks/conm22/[/URL]

.
 

[quote=bsquared;124344]It is available online here:
[URL]http://www.ams.org/online_bks/conm22/[/URL][/quote]

Is this paper the same that R.D. Silverman meant? It is not by Cunningham. Perhaps I am missing something, but I only found the "usual" version of Proth's theorem in it.

[quote=Retep;124368]Is this paper the same that R.D. Silverman meant? It is not by Cunningham. Perhaps I am missing something, but I only found the "usual" version of Proth's theorem in it.[/quote]

It is a book *about* Cunningham numbers. If I remember right, Cunningham's work took place in the early 20th century, and this book incorporates that information, plus a great deal more that has occured since then. I can't help you about the theorems.