## Trending News

# 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

- QCLv 79 years agoFavorite 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.