Elementary proof there are infinitely many primes of the form $4n+1$

Question

My attempt:

$4n+1$ is odd. Thus its decomposition must not contain $2$. Every odd number is either of the form $4k-1$ or $4m+1$.

$(4m+1)(4k-1)$ is never of the form $4n+1$. So $4n+1$ has factors only of type $4k-1$ or $4m+1$.

If nothing is wrong with the above, I then went on to an "Euclid like" proof. Picked $Q$ as the largest integer such that $4Q + 1$ is prime. And picked $N=4(1*2*...*(Q-1)*Q)+1 $

Now comes my biggest doubt. I think $N$ isn't divisible by any number of the form $4m+1$ or $4k-1$. But I can't prove it. It seems obvious, but perhaps it is wrong. If it is correct, then the proof is done, $N$ must be prime and we arrive at the desired contradiction.

What do you think of this? If it is wrong, please do not solve it, just give a hint.

Answer 1

Proofs can be found in standard books, and a proof has been given at least once, probably more often, on MSE. A link to such an MSE proof can be found on the right side of this page, under Related. It starts from $4(n!)^2+1$.

We give a somewhat different proof than the usual one, with a stronger conclusion. After the Hint, part of the proof is hidden, so you need not look at it.

Hint: Consider the Fermat numbers $F_n=2^{2^n}+1$. We will use two facts:

(i) If $m\ne n$, then $F_m$ and $F_n$ are relatively prime and

(ii) Any prime divisor of $F_n$ is of the shape $2^{n} k+1$ (one can do better).

For the first, suppose $m\lt n$, and suppose that $d\gt 1$ is a divisor of $F_m$. Note that $d$ is odd. Then $2^{2^m}\equiv -1\pmod{d}$, and therefore $2^{2^n}\equiv 1\pmod{d}$. Thus $d$ cannot divide $2^{2^n}+1$. For the second, note that if the prime $p$ divides $2^{2^n}+1$, then $2^{2^n}\equiv -1\pmod{p}$. Let $e$ be the smallest positive integer such that $2^e\equiv -1\pmod{p}$. Then $e=2^n$. For a standard argument shows that $e$ divides $2^n$. And if we had $2^{2^c}\equiv -1\pmod{p}$, with $c\lt n$, it would follow that $2^{2^n}\equiv 1\pmod{p}$. Finally, since $2^{p-1}\equiv 1\pmod{p}$, we have $2^n$ divides $p-1$, so $p$ is of the shape $2^nk+1$.

From this we conclude that for any $m$, there are infinitely many primes of the form $2^m k+1$. For let $p_n$ be the smallest prime divisor of $F_n$. The $p_n$ are all distinct, and if $n\ge m$ then $p_n$ is of the shape $2^mk+1$.