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 exist finitely many primes of the form $4n+3$, say $k+1$ of them: $3,p_1,p_2,....,p_k$
Consider $N = 4p_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 $\Rightarrow q_1,...,q_r$ are odd $\Rightarrow q_i \equiv 1\ (\text{mod }4)$ or $q_i ≡ 3\ (\text{mod }4)$
If all $q_1,...q_r$ are of the form $4n+1$, then $(4n+1)(4m+1)=16nm+4n+4m+1 = 4(\cdots) +1$
Therefore, $N=q_1...q_r = 4m+1$. But $N=4p_1..p_k+3$, i.e. $N≡3\ (\text{mod }4)$, $N$ is congruent to $1\ \text{mod }4$ which is a contradiction.
Therefore, at least one of $q_i \equiv 3\ (\text{mod }4)$. Suppose $q_j\equiv 3\ (\text{mod }4)$
$\Rightarrow$ $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 = 4p_1...p_k + 3 \Rightarrow q_j=3$ Contradiction!
If $q_j=3$ ($\neq p_i$, $1\leq i \leq k$) then $q_j | N = 4 p_1...p_k + 3 \Rightarrow 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
 A: There are infinite primes in both the arithmetic progressions $4k+1$ and $4k-1$.
Euclid's proof of the infinitude of primes can be easily modified to prove the existence of infinite primes of the form $4k-1$.
Sketch of proof: assume that the set of these primes is finite, given by $\{p_1=3,p_2=7,\ldots,p_k\}$, and consider the huge number $M=4p_1^2 p_2^2\cdots p_k^2-1$. $M$ is a number of the form $4k-1$, hence by the fundamental theorem of Arithmetics it has a prime divisor of the same form. But $\gcd(M,p_j)=1$ for any $j\in[1,k]$, hence we have a contradiction.
Given that there are infinite primes in the AP $4k-1$, is that possible that there are just a finite number of primes in the AP $4k+1$? It does not look as reasonable, and indeed it does not occur.
Let us define, for any $n\in\mathbb{N}^+$, $\chi_4(n)$ as $1$ if $n=4k+1$, as $-1$ if $n=4k-1$, as $0$ if $n$ is even. $\chi_4(n)$ is a periodic and multiplicative function (a Dirichlet character) associated with the $L$-function
$$ L(\chi_4,s)=\sum_{n\geq 1}\frac{\chi_4(n)}{n^s}=\!\!\!\!\prod_{p\equiv 1\!\!\pmod{4}}\left(1-\frac{1}{p^s}\right)^{-1}\prod_{p\equiv 3\!\!\pmod{4}}\left(1+\frac{1}{p^s}\right)^{-1}. $$
The last equality follows from Euler's product, which allows us to state
$$ L(\chi_4,s)=\prod_{p}\left(1+\frac{1}{p^s}\right)^{-1}\prod_{p\equiv 1\!\!\pmod{4}}\frac{p^s+1}{p^s-1}=\frac{\zeta(2s)}{\zeta(s)}\prod_{p\equiv 1\!\!\pmod{4}}\frac{p^s+1}{p^s-1}. $$
If the primes in the AP $4k+1$ were finite, the limit of the RHS as $s\to 1^+$ would be $0$.
On the other hand,
$$ \lim_{s\to 1^+}L(\chi_4,s)=\sum_{n\geq 0}\frac{(-1)^n}{2n+1}=\int_{0}^{1}\sum_{n\geq 0}(-1)^n x^{2n}\,dx=\int_{0}^{1}\frac{dx}{1+x^2}=\frac{\pi}{4}\color{red}{\neq} 0 $$
so there have to be infinite primes of the form $4k+1$, too.
With minor adjustments, the same approach shows that there are infinite primes in both the APs $6k-1$ and $6k+1$. I have just sketched a simplified version of Dirichlet's theorem for primes in APs.
A: Suppose that there are only fitely many primes of the form $4k+1$, say $p_{1}, ..., p_{n}$, and consider $N =(p_{1} ...p_{n})^{2}+ 1$. $N>p_{i}$, for $1 ≤i≤n$, hence $N$ cannot be prime. Any number of the form $a^{2}+1 $ has, except possibly for the factor $2$, only prime factors of the form $4m+1$.Since division into $N$ by each prime factor of the form $4k+1$ leaves a remainder $1$, $N$ cannot be composite, a contradiction. Hence, the number of primes of the form $4k +1$ must be infinite.
A: 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.
A: The approach we did in high school consisted of two parts.
(a) First prove that all prime divisors of $a^2$ are in the form of $4m+1$.
If $p$ is prime, then
$p|a^2+1 \implies a^2 ≡ -1 \mod p$, so $a^4 ≡ 1 \mod p$
We know $a^{p-1} ≡ 1 \mod p$ from Fermat's little theorem, so $4|p-1$.
(b) There are infinitely many primes in the form of $4m+1$.
Assume the opposite - there is k numbers of that form and let them be $\{p_1, ... , p_k\}$.
Consider the number a = $2*p_1*p_2...*p_k$.
The number $a^2 + 1 = 4*(p_1^2)\cdot(p_2^2)\cdot \ldots\cdot(p_k^2) + 1$ has at least one prime divisor of the form $4m+1$ (which we proved in (a)) and it isn't any of the numbers $p_1,...,p_k$, a contradiction.
Hope this helps, Zlata.
A: 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.))
A: A much simpler way to prove infinitely many primes of the form 4n+1.
Lets define N such that $N = 2^2(5*13*.....p_n)^2+1$ where $p_n$ is the largest prime of the form $4k+1$.  Now notice that $N$ is in the form $4k+1$.  $N$ is also not divisible by any primes of the form $4n+1$ (because k is a product of primes of the form $4n+1$).  
Now it is also helpful to know that all primes can be written as either $4n+1$ or $4n-1$.  This is a simple proof which is that every number is either $4n, 4n+1, 4n+2$ or $4n+3$.  Thus all odd primes are of the form $4n+1$ or $4n+3$, the only prime ones. $4n+3$ can me written as $4n-1$ and thus all odd primes are of the form $4n+1$ or $4n-1$. 
Now there is a theorem (we can prove this if needed) which says $$x^2\equiv-a^2\pmod p$$ then $p\equiv1\pmod4$ or that $4m+1=p$ where a and p are relatively prime
Now another way to state this theorem is that $x^2+a^2=pk$ for some integer k.  Notice that our definition of $N$ is in the form of $x^2+a^2$ so it must equal $pk$ where $p\equiv1\pmod4$.  Thus we have a contradiction and $p_n$ cannot be a largest prime of the form $4n+1$.
A: Actually there is an even more elegant proof that shows that this holds true for all primes>2:
∀ primes,p ∈P & p>2,∃ k∈Q| k=(p-1)/4  or k= (p+1)/4
Proof:
By definition every 4th integer, k ≥ 4, must have 2^2 (2 squared) as a factor.  This means that every other even integer > 2 must have 2^2 as a factor.
For all primes p>2, the prime itself is odd and therefore p-1 and p+1 are both even.  
Since p-1 and p+1 represent consecutive even integers, one and only one of them must have 2^2 as factors and thus (p±1)/4 is an integer.  ∎
This applies to all primes greater than 2.
