Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
This is not true in general (consider $k=1$ for example). You need some additional conditions. Look at Proth's 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 at 2:43

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.

share|cite|improve this answer

This is the simplest case of Pratt certificates for primality - have a look at for a better explanation. (In the notation of the article, your question corresponds to the case where the only $p_i$ is $2$.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.