Sorry, an error occurred while loading the content.

Re: Primality of generalized Proth numbers

Expand Messages
• hleleu ... Define a 2^n-residue modulo m as follows: An integer a is a 2^n-residue modulo m if and only if it exists an integer b such as b^(2^n)=a mod m
Message 1 of 2 , Jan 5, 2005
hleleu
Rewriting your question in a more readable form with some comments:

>>>>>
Define a 2^n-residue modulo m as follows:
An integer a is a 2^n-residue modulo m if and only if it exists an
integer b such as b^(2^n)=a mod m
Obviously if n=1 then we define the quadractic residues.
[not a new definition]

Now, consider the numbers of the form n=k*2^n+1, n and k are
unconstrained. Since Proth number imposes k<2^n, we call these
numbers generalized Proth numbers.
[better be named an arbitrary odd number]

With these definitions we have the following result:
p=k*2^n+1 is prime if and only if there exist exactly k [that is gcd
(p-1,2^n)] integers
comprised between 1 and p-1 who are 2^n-residue modulo p.
<<<<<

> I'm not aware if this result is already known.

It is a special case of a very well known theorem named Euler's
Criterion for solvability of the equation x^n=a(mod p). This
equation is solvable iff a^((p-1)/d)=1(mod p) where d=gcd(p-1,n). If
the equation is solvable then it has exactly d solutions.

Payam
Your message has been successfully submitted and would be delivered to recipients shortly.