Prove that if n is composite, then 2^(n-1) is composite.
EXPERT ANSWER
Suppose that n is composite.
Then there exist numbers p and q such that n = pq, and 1 < p < n, and 1 < q < n.
Then 2^n – 1 = 2^(pq) – 1 = (2^p)^q – 1.
If q is even, then (2^p)^q – 1 factors as a difference of two squares:
(2^p)^q – 1 = ((2^p)^(q/2) – 1)((2^p)^(q/2) + 1)
Note that, since q/2 is an integer, then each factor is an integer; and since p > 1 and q > 1, then ((2^p)^(q/2) – 1) is at least 3, and ((2^p)^(q/2) + 1) is at least 5. Hence 2^n – 1 is composite, because it factors as the product of two integers larger than 1.
On the other hand, if q is odd, then (2^p)^q – 1 factors using the technique for the difference of two odd powers:
(2^p)^q – 1 = (2^p – 1)((2^p)^(q – 1) + (2^p)^(q – 2) + … + (2^p)^1 + 1)
Clearly both factors are integers, and since p > 1, then 2^p – 1 is at least 3, but certainly less than (2^p)^q – 1. Since 2^n – 1 has a factor between 1 and itself, then it is composite.