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

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 - It doesn't work, because it doesn't work. A product of numbers 1 mod 4 can't be 3 mod 4, but a product of numbers 3 mod 4 can be 1 mod 4. There are other methods. – Gerry Myerson Nov 26 '12 at 12:00 @GerryMyerson can you show me a way to prove it? – Amadeus Bachmann Nov 26 '12 at 12:10 Use the Dirichlet's theorem which states that for a pair of numbers a, b satisfying gcd(a,b)=1, then the series {an+b} must contain infinitely many primes. Your problem is pointed out by Gerry Myerson. – lee Nov 26 '12 at 12:12 A prime divisor of$m^2+1$for an integer$m$is either$2$or equal to$1$($\bmod4$). Then your argument can be adapted a bit to show that a finite number of such primes is insufficient to produce all numbers of this form. – WimC Nov 26 '12 at 12:31 @lee, Dirichlet is truly overkill for this problem. – Gerry Myerson Nov 26 '12 at 21:58 ## 2 Answers 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. - Could you explain me how you deduce the equality in the last display? I don't get how it follows from Fermat. How do you exclude the righ hand side to be -1? – Koenraad van Duin Sep 15 at 21:52 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$. (There'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: Wikipedia as a reference.))

-
Didn't you get a warning that you were overriding my edit? –  joriki Nov 26 '12 at 12:30