Primes in the form $ 2^n k +1$

Question

1) Prove that any prime factor of the $n ^{th}$ Fermat number $ 2 ^ {2 ^n}+1$ is congruent to $1$ modulo $ 2^ {n+1}$ . Show that there are infinitely many prime numbers of the form $ 2^n k +1 $ for any fixed $n$.

That was an exercise on brilliant so they did give the solution. I did understand the first part but didn't understand the second one, just the part that those primes had to be in the form of $ 2^n k +1 $ but that's basically the first part, so I would like you to explain me the second part. Thanks in advance.

Answer 1

For the second part, suppose we have an infinite set of positive integers $q_1, q_2 \dots q_n \dots$ and that these integers are pairwise coprime and greater than $1$. Each of the $q_i$ has at least one prime factor - we select one and call it $p_i$.

Now, since the $q_i$ are pairwise coprime we have that $p_m\neq p_n$ - otherwise $q_m$ and $q_n$ would have a common factor.

So we have an infinite set of primes $p_i$.

We apply this to the Fermat numbers by showing that they are pairwise coprime, and we choose these as our $q_i$ and take a prime factor of each as our $p_i$. Then from the first part we know that the $p_i$ all have a specific form, so there are an infinite number of primes having this form.

The second part of the answer concentrates on proving that the Fermat numbers $q_i$ are coprime, and assumes that the rest of the argument is easily completed.

Answer 2

See, the point is that we want to generate infinitely many primes of the form $2^n k + 1$ for a fixed $n$.

Every prime of the form $2^n k +1$ satisfies $p \equiv 1 \mod 2^n$.

So the first paragraph, is just telling us (with a shift of $n \to n-1$)that every prime factor of $2^{2^{n-1}} + 1$ satisfies $p \equiv 1 \mod 2^{n}$. That is, candidates for primes of the form $p \equiv 1 \mod 2^n$ come by taking prime factors of the number $2^{2^{n-1}} + 1$.

What the author has not pointed out, is that if a number is of the form $2^mk + 1$, then for every $n < m$ it is also equal to $2^n \times(2^{m-n}k) + 1$, and hence is also of the form $2^{n}l + 1$ for some different $l$.

Thus, candidates for primes of the form $p \equiv 1 \mod 2^n$ also come by taing prime factors of the numbers $2^{2^m} + 1$ for $m > n -1$. It is therefore enough to show that there are infinitely many primes of this form.

Therefore, the plan of action is this :

• Prove that every pair of Fermat numbers are coprime. This is the last part of the second paragraph, where it is shown that if $d$ divides any two Fermat numbers then it is equal to $1$.

• Therefore, let us call $S_n$ as the set of prime factors of the $n$th Fermat number $F_n$. $S_n$ contains at least one element. Furthermore, every prime in $S_n$ satisfies $p \equiv 1 \mod 2^{n+1}$, and therefore $p \equiv 1 \mod 2^j$ for every $j < n+1$.

• Now, fix $N$. The union of $S_N,S_{N+1},...$ produces an infinite set, since $S_N$ are disjoint, non-empty and infinite in number, and all elements of the union satisfy $p \equiv 1 \mod 2^n$, and hence are of the form $2^n k + 1$ for some $k$.

This shows the proposition. The author has taken a few liberties with his writing, but with a little more practice you will be able to understand arguments like this more easily.