# $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.$$

Fixed.

#### 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).

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$.)