Re: Primality of generalized Proth numbers
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
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.