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 = 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

  • 8
    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$ ($\bmod$ $4$). 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
  • 3
    @lee, Dirichlet is truly overkill for this problem. – Gerry Myerson Nov 26 '12 at 21:58
up vote 24 down vote accepted

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.

  • 1
    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 '14 at 21:52
  • 1
    It's from the $(n!)^{p - 1}$. – zscoder Sep 22 '14 at 13:28

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.))

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=p_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.

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 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$.

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.

  • 2
    This shows that there are infinitely many primes which are of the form $4k \pm 1$, not that there are infinitely many primes of each form individually. Rather, this answer needs only the fact that there are infinitely many odd primes. – T. Bongers Jan 12 '16 at 20:47

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.