Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
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
add comment

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.