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

Apr 2009
96
0
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?
 

chiph588@

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
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
 

chiph588@

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
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 \(\displaystyle 4n+3 \):

-------

Lemma: The product of two integers \(\displaystyle 4n+1 \) and \(\displaystyle 4m+1 \) is an integer of the form \(\displaystyle 4k+1 \)

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

-------

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

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

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

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

Thus since no prime in our list divides \(\displaystyle N \) and we know there is a prime of the form \(\displaystyle 4n+3 \) that does divide \(\displaystyle 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 \(\displaystyle 4n+1 \) for you soon.
 
Last edited:

chiph588@

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
Here's \(\displaystyle 4n+1 \):

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

Let \(\displaystyle p\mid N \). Since \(\displaystyle N \) is odd, \(\displaystyle p\neq2 \). Thus \(\displaystyle (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 \(\displaystyle p\equiv1\bmod{4}\implies p \) is of the form \(\displaystyle 4n+1 \).

Therefore \(\displaystyle p\in\{p_1,\;p_2,\;\ldots,\;p_k\}\implies p\mid(2p_1p_2\cdots p_k)^2 \). So \(\displaystyle 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 \(\displaystyle 4n+1 \).
 
Apr 2009
96
0
Here's \(\displaystyle 4n+1 \):

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

Let \(\displaystyle p\mid N \). Since \(\displaystyle N \) is odd, \(\displaystyle p\neq2 \). Thus \(\displaystyle (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 \(\displaystyle p\equiv1\bmod{4}\implies p \) is of the form \(\displaystyle 4n+1 \).

Therefore \(\displaystyle p\in\{p_1,\;p_2,\;\ldots,\;p_k\}\implies p\mid(2p_1p_2\cdots p_k)^2 \). So \(\displaystyle 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 \(\displaystyle 4n+1 \).

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

chiph588@

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
So how is this manipulated similarly to show 4n-1 primes?
\(\displaystyle 4n+3=4(n+1)-1 \)

Thus my proof for \(\displaystyle 4n+3 \) works for \(\displaystyle 4n-1 \)
 
Apr 2009
96
0
\(\displaystyle 4n+3=4(n+1)-1 \)

Thus my proof for \(\displaystyle 4n+3 \) works for \(\displaystyle 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 ?
 

chiph588@

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
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 \(\displaystyle 4n+3 \) is of the form \(\displaystyle 4m-1 \).

A number of the form \(\displaystyle 4n-1 \) is of the form \(\displaystyle 4m+3 \).

Thus these two forms are equivalent.