$n = 2^k + 1$ is a prime iff $3^{\frac{n-1}{2}} \equiv -1 \pmod n$

Let $k \geq 2$ be a positive integer and let $n=2^k+1$. How can I prove that $n$ is a prime number if and only if
$$3^{\frac{n-1}{2}} \equiv -1 \pmod n.$$


Solutions Collecting From Web of "$n = 2^k + 1$ is a prime iff $3^{\frac{n-1}{2}} \equiv -1 \pmod n$"

Here are two options for finding a proper proof for this theorem (called Pepin’s test).

1) http://en.wikipedia.org/wiki/Pepin's_test.

2) “Solved and Unsolved Problems in Number Theory” by Daniel Shanks.
This book includes the proof for that theorem.

This is the simplest case of Pratt certificates for primality – have a look at http://mathworld.wolfram.com/PrattCertificate.html for a better explanation. (In the notation of the article, your question corresponds to the case where the only $p_i$ is $2$.)