Show that if n is composite, 2n - 1 is composite too.

(Hint: Asume that n = ab and prove that xy = 2n - 1 for the numbers x = 2b- 1 and y = 1 + 2b + 22b + ... + 2(a-1)b)

Solution:

  Assume n = ab where a, b ∈ ℕ
  Let x = 2b - 1 and y = 1 + 2b + 22b + ... + 2(a-1)b

  xy = (2b - 1)(1 + 2b + 22b + ... + 2(a-1)b)
     =        2b + 22b + ... + 2(a-1)b + 2(a-1)b+b
       - (1 + 2b + 22b + ... + 2(a-1)b)
     = 2ab - 1
     = 2n - 1

  This shows that if n is composite, 2n - 1 is also composite since we can always find integers x and y of the form above.

# posted by rot13(Unafba Pune) @ 9:31 PM