Prove that if n is composite, then 2^(n-1) is composite.

28 0

Get full Expert solution in seconds

$1.97 ONLY

Unlock Answer

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.