Is there an Elementary Proof of Proth's Theorem

Question

I am wondering if there is an elementary proof that for an odd $k<2^n$, then $N=k2^n+1$ is prime iff $a^{\frac{N-1}{2}}\equiv -1\mod N$ for some coprime $a$. It is stated that the proof resembles Pépins Test and utilizes Pocklington's method. This is all I could find. Additionally, I am curious as to the necessity of the condition $k<2^n$.

Answer 1

Claim :

The number $N=2^n\cdot k+1$ with $k<2^n$ is prime if and only if there exists $a$ with $a^{(N-1)/2}\equiv -1\mod N$

Proof :

If $N$ is prime, let $a$ be a primitive root of $N$.

Fermat's little theorem gives $a^{N-1}\equiv 1\mod N$ , hence $a^{(N-1)/2}\equiv \pm1\mod N$.

But since $a$ is a primitive root , we cannot have $a^{(N-1)/2}\equiv 1\mod N$

Now suppose, there exists $a$ with $a^{(N-1)/2}\equiv -1\mod N$.

Let $s$ be the order of $N$ modulo $a$, in other words the smallest positive integer with $a^s\equiv 1\mod N$.

Since $a^{N-1}\equiv 1\mod N$ , we have $s\mid N-1$

If we write $s=2^m\cdot p$ with odd $p$ , we cannot have $m<n$ because then we would have $a^{(N-1)/2}\equiv 1\mod N$ because $s$ would divide $(N-1)/2$.

Hence $s$ is at least $2^n$.

If $q$ is a prime factor of $N$, we have $a^{q-1}\equiv 1\mod q$ because $a$ and $q$ must be coprime , and $s$ must be the order of $a$ modulo $q$, otherwise $s$ would not be the order of $a$ modulo $N$.

Hence, we have $s|q-1$. So, we have $q\equiv 1\mod s$ , in particular $q>s$.

Since $s$ is at least $2^n$ and $k<2^n$, we can conclude that every prime factor $q$ must exceed $\sqrt{N}$ and this implies that $N$ must be prime.

The last part requires $k<2^n$