Your proof is almost perfect.
The contradiction comes from assuming were all the primes of the form , then finding the prime and observing .
I have proved that if (2^m) + 1 is prime, then m = 2^n for some n.
Also , I have managed to show that for the nth Fermat number, F_n =
(2^2^n) + 1, if a =/= b, the gcd(F_a, F_b) = 1.
Finally I have shown that if p is prime and p divides F_n, then 2^
(n+1) divides (p-1).
My question is:
How do you deduce that for each n, there are infinitely many primes
congruent to 1(mod 2^n)?
This is how I have approached it so far but am not sure.
Suppose for a contradiction that there are only finitely many primes
congruent to 1 modulo 2^n.
Label them p_1, ..., p_n.
Consider x = 2*p_1...p_n
and N = x^(2^(n-1))+ 1
Because x is divisible by 2, x^2 is congruent to 0 (mod 2^n).
So N is congruent to 1 (mod 2^n).
Also, we note that N is congruent to 1(mod p_i) for each of the p_i.
Assume N is not prime.
Then there exists a prime q such that q divides N = x^(2^(n-1))+ 1.
So x^(2n-1) is congruent to -1(mod q).
=> x^(2n) is congruent to 1(mod q).
=> 2^n divides (q-1) by PART iii
=> q is congruent to 1(mod 2^n)
Thus q is one of the p_i for some i.
(since N is congruent to both 0(mod q) and 1(mod p_i))
=> N is prime
But since N > p_i, and N is congruent to 1 (mod 2^n), this is again
Since either assuming N is prime or assuming N is composite leads to
a contradiction, there must be infinitely many primes congruent to 1
Thanks for your help.