Pre-interview_Test_Question_31

Note that:

\displaystyle a^n - 1 = (a - 1) \sum_{k = 0}^{n - 1} a^k

and in general:

\displaystyle a^n - b^n = (a - b) \sum_{k = 0}^{n - 1} a^k b^{n - 1 - k}

So a^n - 1 is divisible by a - 1. So if a > 2, then a^n - 1 is composite, so a = 2 if a^n - 1 is prime.

Suppose n was composite, eg. n = m k for integers m, k > 1. Then using the identity from before:

\displaystyle 2^{mk} - 1 = (2^m - 1)\sum_{j = 0}^{k - 1} 2^{mj}

So 2^{mk} - 1 is divisible by 2^m - 1. As m > 1, this means that 2^{mk} - 1 is composite.

So 2^n - 1 is composite if n is composite, so if 2^n - 1 is prime n must be prime.

It makes sense to investigate composite n again. Set n = mk with m, k > 0 as before. Then:

\displaystyle 2^{mk} - (-1)^k = (2^m)^k - (-1)^k = (2^m + 1)\sum_{j = 0}^{k - 1} 2^{mj} (-1)^{k - 1 - j}

If k is odd then this implies that 2^{mk} + 1 is divisible by 2^m + 1. That is, composite. Note that for every prime factor of n, we can choose it to fall in either m or k. For 2^n + 1 to be prime, we must have every possible value for k to be even. This is only possible if n has only even factors, otherwise we could take k to be the product of all the odd prime factors of n. That is, n is a power of 2.

(for simplicity, I don’t take prime factors to be distinct, meaning we count, say 2 in 4 twice when saying “the prime factors” of 4)

1 Like