I need help solving a proof! (Please Help)?

The problem states: Prove that 2^(n)+1 cannot be a prime number if n has an odd prime divisor.

I don't even no where to start on this problem and I don't know what an odd prime divisor is, so any help would be greatly appreciated. Thanks.

2 Answers

Relevance
  • QC
    Lv 7
    9 years ago
    Favorite Answer

    Let a be an odd number. Then:

    (x + y) (x^(a-1) − x^(a-2)y + x^(a-3)y^2 − . . . + x^2y^(a-3) − xy^(a-2) + y^(a-1))

    = x (x^(a-1) − x^(a-2)y + x^(a-3)y^2 - . . . + x^2y^(a-3) − xy^(a-2) + y^(a-1))

    + y (x^(a-1) − x^(a-2)y + x^(a-3)y^2 - . . . + x^2y^(a-3) − xy^(a-2) + y^(a-1))

    = (x^a − x^(a-1)y + x^(a-2)y^2 − . . . + x^3y^(a-3) − x^2y^(a-2) + xy^(a-1))

    . . . . . + (x^(a-1)y − x^(a-2)y^2 + x^(a-3)y^3 − . . . + x^2y^(a-2) − xy^(a-1) + y^a)

    = x^a + y^a

    -------------------------

    Let n have an odd prime divisor

    Then n = p*k, where p is an odd prime number, and k is a positive integer

    2^n + 1 = 2^(p*k) + 1 = (2^k)^p + 1

    Since p is odd, we can factor (2^n + 1) as follows:

    (2^k + 1) ((2^k)^(p-1) − (2^k)^(p-2) + (2^k)^(p-3) − . . . + (2^k)^2 − (2^k) + 1)

    Check:

    (2^k + 1) ((2^k)^(p-1) − (2^k)^(p-2) + (2^k)^(p-3) − . . . + (2^k)^2 − (2^k) + 1)

    = 2^k ((2^k)^(p-1) − (2^k)^(p-2) + (2^k)^(p-3) − . . . + (2^k)^2 − (2^k) + 1)

    + 1 ((2^k)^(p-1) − (2^k)^(p-2) + (2^k)^(p-3) − . . . + (2^k)^2 − (2^k) + 1)

    = ((2^k)^p − (2^k)^(p-1) + (2^k)^(p-2) − . . . + (2^k)^3 − (2^k)^2 + (2^k))

    . . . . . . . . + ((2^k)^(p-1) − (2^k)^(p-2) + (2^k)^(p-3) − . . . + (2^k)^2 − (2^k) + 1)

    = (2^k)^p + 1

    = 2^(k*p) + 1

    = 2^n + 1

    So 2^k + 1 is a factor of 2^n + 1

    We just need to show that 2^k + 1 is not equal to 1 or 2^n + 1

    k ≥ 1

    2^k ≥ 2

    2^k + 1 ≥ 3

    2^k + 1 ≠ 1

    n = p*k, where p is odd prime number ----->

    p ≥ 3

    k ≠ n

    2^k + 1 ≠ 2^n + 1

    2^k + 1 is a factor of 2^n + 1

    2^k + 1 ≠ 1, 2^k + 1 ≠ 2^n + 1

    Therefore 2^n + 1 is not prime

    -- Ματπmφm --

  • 9 years ago

    And odd number is a number n = 2k + 1 for some non-negative integer k.

    Suppose n has a an odd prime divisor. Then n can be written in the form n = a _1^(b_1)*a _2^(b_2)...(2k + 1 )^m...a_q^(b_q) where 2k + 1 is prime. You want to prove that 2^(n) + 1 cannot be prime. I would try proof by contradiction. Assume it is prime, and get a contradiction.

Still have questions? Get your answers by asking now.