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

• This is not true in general (consider $k=1$ for example). You need some additional conditions. Look at Proth's theorem. en.wikipedia.org/wiki/Proth%27s_theorem – Siva Apr 14 '11 at 7:22
• Note that one needs to ask that $k \ge 2$. – André Nicolas Apr 14 '11 at 7:24
• The title of the question is misleading. – lhf Sep 8 '11 at 17:16
• @lhf: I changed the title as I agree the title was misleading. One could maybe add $k \geq 2$ to the title as well, but I'm not sure if the title doesn't become too long then. – TMM Sep 28 '11 at 14:21
• The easier half of this proposition is established for this newer Question. Since neither implication is really detailed here, I don't see treating either of these Questions as a duplicate. – hardmath Jun 6 '16 at 2:43

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