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.

  • 1
    This is not true in general (consider $k=1$ for example). You need some additional conditions. Look at Proth's theorem. http://en.wikipedia.org/wiki/Proth%27s_theorem2011-04-14
  • 1
    Note that one needs to ask that $k \ge 2$.2011-04-14
  • 2
    The title of the question is misleading.2011-09-08
  • 0
    @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.2011-09-28
  • 0
    The easier half of this proposition is established for [this newer Question](http://math.stackexchange.com/questions/1815066/prove-that-3q-1-2-equiv-1-pmod-q-then-q-is-prime-number). Since neither implication is really detailed here, I don't see treating either of these Questions as a duplicate.2016-06-06

2 Answers 2

7

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.

5

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