Prove that if n is composite then 2^n - 1 is composite?

Hi Froskoy,

Let n = j * k, for some integers j and k both exceeding 1.

2^(n) - 1 = 2^(jk) - 1 = (2^(j))^(k) - 1.

= (2^(j) - 1) [(2^(j))^(k - 1) + (2^(j))^(k - 2) + (2^(j))^(k - 3) + .. + 1].

Now, for j > 1, you have 2^(j) > 2, thus 2^(j) - 1 > 1.

The other factor is a sum of powers, which can never be negative, with the smallest possible total for k > 1 being:

[(2^(j))^(k - 1) + 1] = [(number greater than 2)^(k - 1) + 1].

Notice k > 1 so k - 1 > 0.

= [(number greater than 2)^(number greater than 0) + 1] > 1.

So, this is a product of two factors, both greater than 1.

Therefore, this is composite.

-----

Note that this is a one-way proof. If 2^(n) - 1 is composite, it tells you nothing about n.

Examples:

2^(11) - 1 = 2048 - 1 = 2047 = 23 * 89 composite.

Here n = 11 (prime).

2^(4) - 1 = 16 - 1 = 15 = 3 * 5 composite.

Yet here n = 4 (composite).

The statement is obvious true when n is even since n^4 + 4^n will be an even number greater than 2. Also, if n > 1 and n = 10k + 1, 10k +3, 10k + 7 or 10k +9, let t = 1, 3, 7, or 9, we will have n^4 = (10k + t)^4 = 1 mod 10 and 4^(10k + t) = 4 mod 10, so n^4 + 4^n = 5 mod 10 i.e., it's divisible by 5, so it's composite. Finally, for n = 10k + 5, observe that n^4 + 4^n = (n^2)^2 + (2^n)^2 and (n^2 + 2^n)^2 = n^4 + 4^n + 2(n^2)(2^n) i.e., n^4 + 4^n = (n^2 + 2^n)^2 - 2(n^2)(2^n) = (n^2 + 2^n)^2 - n^2*2^(n+1). But n^2*2^(n+1) is a perfect square since n^2 is a square and 2^(n+1) is also a square since n=10k +5 is odd, so it makes (n^2 + 2^n)^2 - (n^2)(2^(n+1)) a difference of two squares, which is factorable. So n^4 + 4^n is composite when n=10k +5. [Note: I actually can include all n = 2k + 1 = odd in this paragraph and omit the 2nd paragraph I wrote, but I didn't realize the difference of two squares until I single out the case when n = 10k +5, but anyway the proof is complete. ]

First note that aᵐ - bᵐ is divisible by a-b because

aᵐ - bᵐ = (a-b)(aᵐˉ¹ + aᵐˉ²b+...+abᵐˉ²+bᵐˉ¹)

If n is composite then n can be written as n=mk where m and k are integers. So

2ⁿ -1 = 2ᵐᵏ - 1ᵐᵏ = (2ᵏ)ᵐ - (1)ᵐ

= (2ᵏ -1)((2ᵏ)ᵐˉ¹ + (2ᵏ)ᵐˉ²+...+(2ᵏ)+1)

So it is divisible by (2ᵏ -1) and therefore composite.