Are Primes of the Form 4n+1 Infinite?

In summary, a conversation took place discussing the infiniteness of primes of the form 4n+1 and 4n+3. It was mentioned that primes of the form 4n+3 are infinite, but there was no proof for the infiniteness of primes of the form 4n+1. An indirect proof by contradiction was presented to prove that primes of the form 4n+1 are also infinite, using Euler's Criterion for Quadratic Residues. It was also mentioned that there are no examples of primes of a particular form that are finite in number, with the exception of 2, and the set of primes that cannot be written as the sum of two or more primes. The conversation ended with a joke
  • #1
tamalkuila
4
0
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.please help


prove that primes of the form 4n+1 are infinite.
 
Physics news on Phys.org
  • #2
are you trying to do:
[tex]\sum_{n=1}^{\infty} 4(n+1)=\infty[/tex]
 
  • #3
Are you saying that an expression:
[tex]4n+3 = p [/tex]

will produce a prime for every value of [tex] n [/tex]?

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
p53ud0 dr34m5 said:
are you trying to do:
[tex]\sum_{n=1}^{\infty} 4(n+1)=\infty[/tex]

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

FrogPad said:
Are you saying that an expression:
p= 4n+3 will produce a prime for every value of n?

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
tamalkuila said:
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.please help


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

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
tamalkuila said:
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.please help


prove that primes of the form 4n+1 are infinite.
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):

[tex] 1: \ \ \ \ Q \ = \ \prod_{j = 1}^{R} \, (4n_{j}+1) [/tex]

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

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

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

[tex] 3: \ \ \ \, (1 + Q^{2}) \ \cong \ 0 \mod(P) [/tex]

[tex] 4: \ \ \ \ \Longrightarrow \ \ Q^{2} \ \cong \ -1 \mod(P) [/tex]

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:

[tex] 5: \ \ \ \ (-1)^{(P - 1)/2} \ \cong \ 1 \mod(P) [/tex]

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

[tex] 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}*** } [/tex]

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 by a moderator:
  • #7
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
saltydog said:
(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?
[tex]p=2n~,~~ n~ \epsilon~ \mathbb{N} [/tex] :wink:
 
  • #9
Gokul43201 said:
[tex]p=2n~,~~ n~ \epsilon~ \mathbb{N} [/tex] :wink:

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
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. :biggrin:
 
  • #11
Gokul43201 said:
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. :biggrin:

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

Related to Are Primes of the Form 4n+1 Infinite?

1. What are "Primes of the form 4n+1"?

"Primes of the form 4n+1" are a specific type of prime number that can be expressed in the form of 4n+1, where n is an integer. These primes have the unique property of being one more than a multiple of 4, and they are denoted by the symbol p = 4n+1.

2. What makes "Primes of the form 4n+1" significant?

"Primes of the form 4n+1" are significant because they play a crucial role in number theory and have important applications in cryptography. They are also closely related to the Gaussian integers, which are complex numbers with integer real and imaginary parts.

3. How can we determine if a number is a "Prime of the form 4n+1"?

To determine if a number is a "Prime of the form 4n+1", we can use a variety of methods such as trial division, sieving methods, or the Miller-Rabin primality test. However, there is no known formula or algorithm that can generate all "Primes of the form 4n+1" efficiently.

4. Why are "Primes of the form 4n+1" important in cryptography?

"Primes of the form 4n+1" are essential in cryptography because they are used in the generation of public and private keys for secure communication. They also play a crucial role in the RSA encryption algorithm, which is widely used in modern communication systems.

5. What are some examples of "Primes of the form 4n+1"?

Some examples of "Primes of the form 4n+1" include 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, and many more. These primes are used extensively in number theory and cryptography due to their unique properties and applications.

Similar threads

Replies
5
Views
1K
  • Introductory Physics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Introductory Physics Homework Help
Replies
5
Views
1K
  • Introductory Physics Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
11
Views
981
Replies
4
Views
978
  • Introductory Physics Homework Help
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
Replies
1
Views
491
Back
Top