Converse of Proth's Theorem

[Dougy]

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

[akruppa]

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

[Dougy]

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.

[Retep]

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.

[R.D. Silverman]

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.

[Retep]

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.

[R.D. Silverman]

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.

[Retep]

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.

[akruppa]

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

[Retep]

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

[Retep]

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.