from.4 MI

(a) Let P(n) : x^(2n-1) + 1 is divisible by x + 1 for all positive integer n
First prove n = 1,
x^1 + 1 is divisible by x + 1, it is obvious
Second assume x^(2k-1) + 1 is divisible by x + 1, i.e. x^(2k-1) + 1 = P(x)(x + 1) where P(x) is a polynomial in x
Then (x^2)[x^(2k-1) + 1] = P(x)(x^2)(x + 1)
x^(2k+1) + x^2 = P(x)(x^2)(x + 1)
x^[2(k+1)-1] + 1 = P(x)(x^2)(x + 1) + 1 - x^2
x^[2(k+1)-1] + 1 = P(x)(x^2)(x + 1) + (1 - x)(1 + x)
x^[2(k+1)-1] + 1 = [P(x)(x^2) + (1 - x)](x + 1) is divisible by x + 1 thus proved.
(b) Let us assume that it does not need n = 2^m in order to make 2^n + 1 a prime number ... assumption (A)
For any odd number n, it has been shown in (a) that (2 + 1) is a factor, so that 2^n + 1 cannot be prime when n is odd.
Now for an even number, we can divide the number by 2 successively until the quotient becomes odd. Suppose the number n can be divided by 2 for p times when the quotient reaches an odd number k where k > 1.
So n = (2^p)K (example 30 = 2*15; 28 = 2^2*7; 36 = 2^2*9; 72 = 2^3*9)
Then 2^n + 1 = 2^[(2^p)K] + 1
= [2^(2^p)]^K + 1
This is shown in part (a) that x^K + 1 has a factor of x + 1 for odd number K. Consider x = 2^(2^p)
2^(2^p) + 1 is a factor of [2^(2^p)]^K + 1 => 2^n + 1 is not a prime contradicting assumption (A).
Therefore the conclusion is that in order for 2^n + 1 to be prime, it is a must that n = 2^m for some integer m.
On the contrary, we cannot prove that if n = 2^m then 2^n + 1 must be a prime.
Indeed it is not, for example, when n = 2^5 or n = 32,
2^32 + 1 = 4294967297 = (641)(6700417)

then n=2^m for some integer m
n=2^m!!!!
for some integer m!!!!
when m = 0??

a) when n=1 ,

x^(1)+1=(x+1) , so it is true for n=1

Assume it is true for n=k , where k is a positive integer ,

i.e. x^(2k-1)+1=(x+1)p(x) , where deg p(x) = 2k-2 and all coef are real,

Consider n=2k+1 ,

x^(2k+1)+1

=x^(2k-1) x^2+1

=[(x+1)p(x)-1]x^2+1

=x^2(x+1)p(x)-(x^2-1)

=x^2(x+1)p(x)-(x+1)(x-1)

=(x+1)[x^2 p(x)-(x-1)] ,

so it is true for n=2k+1

By Mathematical induction , it is true for all +ve odd integer n.

b)2^n+1 is a prime number

=> 2^n+1 can not be divided by any number

=> n must be even (by a)

=> n =2m , where m is a integer.