# Primes of the form 4n+1

1. May 1, 2005

### tamalkuila

I have proved the primes of the order 4n+3 are infiinite but can not prove that primes of the form 4n+1 are infinite.plz help

prove that primes of the form 4n+1 are infinite.

2. May 1, 2005

### p53ud0 dr34m5

are you trying to do:
$$\sum_{n=1}^{\infty} 4(n+1)=\infty$$

3. May 1, 2005

Are you saying that an expression:
$$4n+3 = p$$

will produce a prime for every value of $$n$$?

Because this is definitely not right. Here are a few counters:
n = 3
p = 15 (not prime)

n = 6
p = 27 (not prime)

.
.
.
n = 1001
p = 4011 (not prime) ... divides by 3

Or, are you just saying that there is an infinite amount of primes that exist in the form 4n+3 = p. ie:
n = 4
p = 11
Thus p is prime in the form (4n+3) and there exists an infinite amount of these primes.

Actually this is probably exactly what you are saying. So, how about you give some type of work on how you think you should solve your latter question. Or, how did prove the first form?

4. May 1, 2005

### HallsofIvy

Staff Emeritus
Why would you think that? That's obviously true.

No, he didn't say anything of the kind. I don't see how you could interpret what he did say that way.

What he said was that he can prove "the set of all primes of the form 4n+3 is infinite" or, equivalently "there exist an infinite number of primes that are of the form 4n+3". Not that all numbers of the form 4n+3 are prime, but that an infinite number of them are.

What he is asking about is how to prove "the set of all primes of the form 4n+1 is infinite" or, equivalently "there exist an infinite number of primes that are of the form 4n+1".

5. May 1, 2005

### saltydog

Well Tamalkuila, I have two questions but don't want to get you off track so please do as you wish and I won't take offense:

(1) Care to share with us the proof for primes of the form 4n+3 are infinite?

(2) I'm very curious about this one: Has anyone proven that there are primes of a particular form that ARE NOT infinite in number? If so, can you or someone else give me an example?

6. May 1, 2005

### xanthym

This is an indirect proof by contradiction. We first presume that only a finite number "R" of primes have form (4*nj + 1), where {nj, j=1,2,3,...,R, ∈ Integers}. We define integer "Q" with the following, where the product is over all "R" primes of form (4*nj + 1):

$$1: \ \ \ \ Q \ = \ \prod_{j = 1}^{R} \, (4n_{j}+1)$$

Now consider the integer "T" defined by the following:

$$2: \ \ \ \ T \ = \ 1 + Q^{2} \ = \ 1 \ + \ \left ( \prod_{j = 1}^{R} \, (4n_{j}+1) \right )^{\displaystyle 2}$$

There exists an odd prime "P" which divides "T", so that:

$$3: \ \ \ \, (1 + Q^{2}) \ \cong \ 0 \mod(P)$$

$$4: \ \ \ \ \Longrightarrow \ \ Q^{2} \ \cong \ -1 \mod(P)$$

Since "P" is an odd prime and gcd{P,(-1)}=(1), Eq #4 implies that (-1) is a Quadratic Residue of "P". Thus, Euler's Criterion applies:

$$5: \ \ \ \ (-1)^{(P - 1)/2} \ \cong \ 1 \mod(P)$$

Eq #5 is only true if {(P - 1)/2} is even. All odd primes have either the form (4*n + 1) or (4*n + 3). Thus, this odd prime "P" must have the form (4*n + 1) to make {(P - 1)/2} even. Hence, by Eq #1's definition of "Q", this prime "P" of form (4*n + 1) must divide "Q".

However, by definition, this "P" also divides T=(1 + Q2):

$$6: \ \ \ \ P \ \textsf{\color{blue}divides} \ \left \{ \begin{array}{c} Q \\ \textsf{and} \\ 1 + Q^{2} \\ \end{array} \right \} \ \ \Longrightarrow \ \ P \textsf{ \color{blue} divides } (1) \ \ \textsf{ \color{red} \LARGE ***\underline{CONTRADICTION}*** }$$

Thus, the original presumption of only a finite number of (4*n + 1) primes is NOT correct.
Q.E.D.

(Note: Above proof utilized Euler's Criterion for Quadratic Residues. This theorem's proof can be found at the Web Site shown below.)
http://planetmath.org/encyclopedia/ProofOfEulersCriterion.html

~~

Last edited: May 2, 2005
7. May 2, 2005

halls:
Yeah, I started typing a reply and then half way through I realized that what I was typing didn't make any sense. I should have just removed the first half of my post... however, the post was not "precise". There WAS room for interpretation. I definitely interpretted it wrong. Your response however was 100% clear. Anyways, seems xanthym cleared it up...

8. May 3, 2005

### Gokul43201

Staff Emeritus
$$p=2n~,~~ n~ \epsilon~ \mathbb{N}$$

9. May 3, 2005

### saltydog

Yea, 2. Figured someone might bring that up. Thanks. How about another relation concerning the set of primes of a particular form? I suspect there is not a single one that is "finite" Got any?

10. May 4, 2005

### Gokul43201

Staff Emeritus
Hey, no need to get upset. That was just a joke (see the winking guy ?)...albeit a poor one.

Here's another cheat : the set of all primes that can not be written as the sum of two or more primes.

With that, I'll stop being an annoying pest.

11. May 4, 2005

### saltydog

Alright, I was wrong. You're right. I dare not ask for another one. Thanks.