2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Siva Apr 14 '11 at 7:22
  • 1
    $\begingroup$ Note that one needs to ask that $k \ge 2$. $\endgroup$ – André Nicolas Apr 14 '11 at 7:24
  • 2
    $\begingroup$ The title of the question is misleading. $\endgroup$ – lhf Sep 8 '11 at 17:16
  • $\begingroup$ @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. $\endgroup$ – TMM Sep 28 '11 at 14:21
  • $\begingroup$ 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. $\endgroup$ – hardmath Jun 6 '16 at 2:43
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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