proof, composite nums?

If n>1 is an integer not of the form 6k+3, prove n^2+2^n is composite.

1 Answer

Relevance
  • 1 decade ago
    Favorite Answer

    If n > 1, n^2 + 2^n is at least 8.

    If n is even, then n^2 and 2^n are both even, so the sum is even and divisible by 2.

    If n > 1 is odd but not of the form 6k+3, it is of the form 6k+5 or 6k+7. Then n^2 is of the form 3p+1, and 2^n is of the form 3q+2 (see below). The sum is 3(p+q+1), which is divisible by 3.

    To see that 2^n is of the form 3q+2, it is easy to verify this for n = 5 ( 2^5 = 32 = 3×10+2) and n = 7 (2^7 = 128 = 3×42+2). Being of the form 3q+2 is preserved when n goes up by 6; for assuming 2^n = 3q+2, we have 2^(n+6) = 2^6 × 2^n = 64(3q+2) = 3(64q+42)+2. So it holds for all n of one of the forms 6k+5 and 6k+7.

    (This can be presented more elegantly using modular arithmetic and congruence notation.)

Still have questions? Get your answers by asking now.