1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primes of the form 4n+1

  1. May 1, 2005 #1
    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. jcsd
  3. May 1, 2005 #2
    are you trying to do:
    [tex]\sum_{n=1}^{\infty} 4(n+1)=\infty[/tex]
     
  4. May 1, 2005 #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?
     
  5. May 1, 2005 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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".
     
  6. May 1, 2005 #5

    saltydog

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  7. May 1, 2005 #6

    xanthym

    User Avatar
    Science Advisor

    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: May 2, 2005
  8. May 2, 2005 #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...
     
  9. May 3, 2005 #8

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    [tex]p=2n~,~~ n~ \epsilon~ \mathbb{N} [/tex] :wink:
     
  10. May 3, 2005 #9

    saltydog

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  11. May 4, 2005 #10

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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:
     
  12. May 4, 2005 #11

    saltydog

    User Avatar
    Science Advisor
    Homework Helper

    Alright, I was wrong. You're right. I dare not ask for another one. Thanks. :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Primes of the form 4n+1
Loading...