Infinitely number of primes in the form 4n+1 proof

Question

Question: Are there infinitely many primes of the form 4n+3 and 4n-1?

My attempt: Suppose the contrary that there exists finitely many primes of the form 4n+3, say k+1 of them: 3,$p_1,p_2,....,p_k$

Consider $N$ = 4$p_1p_2p_3...p_k$+3 $N$ cannot be a prime of this form. So suppose that $N$=$q_1...q_r$ where $q_i∈P$

Claim: At least one of the $q_i$'s is of the form 4n+3:

Proof for my claim: $N$ is odd => $q_1,...,q_r$ are odd => $q_i$ ≡ 1 (mod 4) or $q_i# ≡ 3 (mod 4)

If all $q_1,...q_r$ are of the form 4n+1, then (4n+1)(4m+1)=16nm+4n+4m+1 = 4() +1

Therefore, $N=q_1...q_r$ = 4m+1. But $N=4p_1..p_k$+3 i.e. $N$≡3 (mod 4), N is congruent to 1 mod 4 which is a contradiction.

Therefore, at least one of $q_i$ ≡ 3 (mod 4). Suppose $q_j$ ≡ 3 (mod 4)

=> $q_j=p_i$ for some 1$\leq$i $\leq$ k or $q_j$ =3

If $q_j=p_i≠3$ then $q_j$ | $N$ = 4$p_1...p_k$ + 3 => $q_j$=3 Contradiction!

If $q_j$=3 (≠$p_i$ , 1$\leq$i $\leq$ k) then $q_j$ | $N$ = 4$p_1...p_k$ + 3 => $q_j=p_t$ for some 1$\leq$i $\leq$ k Contradiction!

In fact, there must be also infinitely many primes of the form 4n+1 (according to my search), but the above method does not work for its proof. I could not understand why it does not work. Could you please show me?

Regards

Answer 1

Suppose $n>1$ is an integer. We define $N=(n!)^2 +1$. Suppose $p$ is the smallest prime divisor of $N$. Since $N$ is odd, $p$ cannot be equal to $2$. It is clear that $p$ is bigger than $n$ (otherwise $p \mid 1$). If we show that $p$ is of the form $4k+1$ then we can repeat the procedure replacing $n$ with $p$ and we produce an infinite sequence of primes of the form $4k+1$.

We know that $p$ has the form $4k+1$ or $4k+3$. Since $p\mid N$ we have $$ (n!)^2 \equiv -1 \ \ (p) \ . $$ Therefore $$ (n!)^{p-1} \equiv (-1)^{ \frac{p-1}{2} } \ \ (p) \ . $$ Using Fermat's little Theorem we get $$ (-1)^{ \frac{p-1}{2} } \equiv 1 \ \ (p) \ . $$ If $p$ was of the form $4k+3$ then $\frac{p-1}{2} =2k+1$ is odd and therefore we obtain $-1 \equiv 1 \ \ (p)$ or $p \mid 2$ which is a contradiction since $p$ is odd.

Answer 2

There's indeed another elementary approach:

For every even $n$, all prime divisors of $n^2+1$ are $ \equiv 1 \mod 4$. This is because any $p\mid n^2+1$ fulfills $n^2 \equiv -1 \mod p$ and therefore $\left( \frac{-1}{p}\right) =1$, which is, since $p$ must be odd, equivalent to $p \equiv 1 \mod 4$.

Assume that there are only $k$ primes $p_1,...,p_k$ of the form $4m+1$. Then you can derive a contradiction from considering the prime factors of $(2p_1...p_k)^2+1$.

(Thee's also an elementary approach to show that there are infinitely many primes congruent to 1 modulo n for every n, but that one gets rather tedious. (See: http://en.wikipedia.org/wiki/Cyclotomic_polynomial#Applications as a reference).)