Browse Groups

• ## Re: Primality of generalized Proth numbers

(2)
• NextPrevious
• 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
View Source
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
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.