# Math Help - Infinitely many primes with either 4n-1 or 4n+1 ... Questions ...

1. ## Infinitely many primes with either 4n-1 or 4n+1 ... Questions ...

Hello All,

My book says that "There are infinitely many primes of the form 4n-1 and 4n+1". The problem is my book doesn't provide proof that this is true.

I've done some research, and it seems like Dirichlet's Theorem is plausible, but there should be an easier way to understand this that covers both examples.

Can anyone prove both of these in an easy way?

2. Originally Posted by 1337h4x
Hello All,

My book says that "There are infinitely many primes of the form 4n-1 and 4n+1". The problem is my book doesn't provide proof that this is true.

I've done some research, and it seems like Dirichlet's Theorem is plausible, but there should be an easier way to understand this that covers both examples.

Can anyone prove both of these in an easy way?
4n-1

4n+1

3. Originally Posted by chiph588@

I looked there and other places google had spat out. I'm looking to see if there is an easier way of explaining it, and also a better way of formatting it as well...

4. Originally Posted by 1337h4x
I looked there and other places google had spat out. I'm looking to see if there is an easier way of explaining it, and also a better way of formatting it as well...
First I'll do $4n+3$:

-------

Lemma: The product of two integers $4n+1$ and $4m+1$ is an integer of the form $4k+1$

Proof: $(4n+1)(4m+1)=16nm+4n+4m+1=4(4nm+n+m)+1=4k+1$, as we choose to define $k=4nm+n+m$.

-------

Now suppose there are finitely many primes of the form $4n+3$ where the list is $\{p_0=3,\; p_1=7,\; p_2,\; \ldots,\; p_k \}$ where $p_k$ is the largest prime of the form $4n+3$.

Define $N=4p_1p_2\cdots p_k+3$ (note that $N$ is odd and we're leaving out $p_0$ from $N$). Since $N$ is of the form $4n+3$, $N>p_k \implies N$ is composite. So let's look at its prime factors. If all prime factors were of the form $4m+1$ then by the Lemma above, $N$ would also have the form $4m+1$. This means we know there is at least one prime of the form $4n+3$ that divides $N$.

Suppose $3\mid N \implies 3\mid N-3 \implies 3\mid 4p_1p_2\cdots p_k$. Since $3$ can't divide $4p_1p_2\cdots p_k$ we see $3$ doesn't divide $N$.

Now suppose $p_i\mid N$ for some $p_i\in \{p_1,\; p_2,\ldots,\;p_k\}$, then $p_i\mid N\implies p_i\mid N-4p_1p_2\cdots p_k = 3$, but clearly $p_i$ can't divide $3$.

Thus since no prime in our list divides $N$ and we know there is a prime of the form $4n+3$ that does divide $N$, we see that we've left a prime out of the list. This means our list is incomplete.

Now observe that this implies there are an infinite amount since if we add in our missing prime to our list, we can do this whole process again and see we're missing another prime again, and so on and so on...

I'll do the primes of the form $4n+1$ for you soon.

5. Here's $4n+1$:

Again, assume there are only finitely many primes of the form $4n+1$. Define $N=(2p_1p_2\cdots p_k)^2+1$, where $\{p_1,\;p_2,\;\ldots,\;p_k\}$ is the set of the primes of the form $4n+1$. Since $N$ is of the form $4n+1$, $N>p_k \implies N$ is composite.

Let $p\mid N$. Since $N$ is odd, $p\neq2$. Thus $(2p_1p_2\cdots p_k)^2+1\equiv0\bmod{p}\implies (2p_1p_2\cdots p_k)^2\equiv-1\bmod{p}\implies x^2\equiv-1\bmod{p}$ is solvable. By your post here, we see that this implies $p\equiv1\bmod{4}\implies p$ is of the form $4n+1$.

Therefore $p\in\{p_1,\;p_2,\;\ldots,\;p_k\}\implies p\mid(2p_1p_2\cdots p_k)^2$. So $p\mid N-(2p_1p_2\cdots p_k)^2=1$ which is a contradiction. Using the same reasoning as in the above post, we see that there are an infinite amount of primes of the form $4n+1$.

6. Originally Posted by chiph588@
Here's $4n+1$:

Again, assume there are only finitely many primes of the form $4n+1$. Define $N=(2p_1p_2\cdots p_k)^2+1$, where $\{p_1,\;p_2,\;\ldots,\;p_k\}$ is the set of the primes of the form $4n+1$. Since $N$ is of the form $4n+1$, $N>p_k \implies N$ is composite.

Let $p\mid N$. Since $N$ is odd, $p\neq2$. Thus $(2p_1p_2\cdots p_k)^2+1\equiv0\bmod{p}\implies (2p_1p_2\cdots p_k)^2\equiv-1\bmod{p}\implies x^2\equiv-1\bmod{p}$ is solvable. By your post here, we see that this implies $p\equiv1\bmod{4}\implies p$ is of the form $4n+1$.

Therefore $p\in\{p_1,\;p_2,\;\ldots,\;p_k\}\implies p\mid(2p_1p_2\cdots p_k)^2$. So $p\mid N-(2p_1p_2\cdots p_k)^2=1$ which is a contradiction. Using the same reasoning as in the above post, we see that there are an infinite amount of primes of the form $4n+1$.

So how is this manipulated similarly to show 4n-1 primes?

7. Originally Posted by 1337h4x
So how is this manipulated similarly to show 4n-1 primes?
$4n+3=4(n+1)-1$

Thus my proof for $4n+3$ works for $4n-1$

8. Originally Posted by chiph588@
$4n+3=4(n+1)-1$

Thus my proof for $4n+3$ works for $4n-1$
I would like to understand how this works. I understand how you did 4n+3 = 4(n+1)-1 because that is 4n+4-1= 4n+3, but are you essentially treating (n+1) as a specific (n) and then stating that 4(n)-1 works for all primes ?

9. Originally Posted by 1337h4x
I would like to understand how this works. I understand how you did 4n+3 = 4(n+1)-1 because that is 4n+4-1= 4n+3, but are you essentially treating (n+1) as a specific (n) and then stating that 4(n)-1 works for all primes ?
A number of the form $4n+3$ is of the form $4m-1$.

A number of the form $4n-1$ is of the form $4m+3$.

Thus these two forms are equivalent.