Primality testing

Question

I have this way of testing for primes greater than 2.

I divide $2^{n-1} - 1$ by n. If the remainder is 0, n is a prime.

This works because in GF(p), if one multiplies all the non-zero elements in the field by the same non-zero number (say 2), all the numbers are simply reordered.

So, if one multiplies the products together, the product is the same as if one had not multiplied by the chosen field element. So, $2^{p-1}$ is congruent to 1 modulo p.

What I'm not sure about is the "only if". If p is prime $2^{p-1} - 1$ is congruent to 0 modulo p. However, it does not mean that if $2^{p-1} - 1$ is congruent to 0 modulo p, p is prime.

Can you help me come up with a proof of the "only if" part?

Incidentally, $2^{n-1} - 1$ is all 1's in binary.

Answer 1

$561 = 3\cdot 11\cdot 17$ is composite, but passes your test (and also passes it for any base other than $2$ as well).

Answer 2

HINT.-Look at the Carmichael numbers to learn you are wrong. I appreciate your efforts and enthusiasm.

Answer 3

Your "test" isn't deterministic. Yes, it does hold for all odd primes $p$ that $2^{p-1} = 1 \pmod p$, however Poulet Numbers pass the test as well, and are composite. We can't rely on this to prove a number is prime, however, (for large numbers) it is extremely likely that an integer satisfying this condition will be a prime. GF$(p)$ is a finite field with $p-1$ elements when $p$ is prime. It is the splitting field of the polynomial $X^p-X$, which contains all of its elements as roots. Another way to state this is:

$X^p-X$ is a multiple of $p$ for all integers $X$ if $p$ is prime.

$X^p-X = 0 \pmod p$.

$X^p = X \pmod p$.

$X^{p-1} = 1 \pmod p$ whenever $X ≠ 0 \pmod p$.

For the latter condition, replacing the requirement that $X ≠ 0 \pmod p$ with $\gcd(X, p)=1$, there are infinitely many composite integers with the same properties (also known as Carmichael Numbers). If you wish to make the $2^{p-1} \pmod p$ test stronger and more efficient, you should use a version of the Miller Rabin Test for base 2.