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!

Proof about 6k+5 producing an infinite amount of primes

  1. May 4, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove that 6k+5 produces an infinite amount of primes. k is an integer
    3. The attempt at a solution
    We first observe that 6k+1,6k+3,6k+5 produce all the odd integers.
    Next we see that (6k+1)(6k'+1)=6(6kk'+k+k')+1 so the product of integers of the form
    (6k+1)(6k'+1)=6k''+1. And we see that 6k+3 is divisible by 3 so it never produces primes.
    when k=1 we see that 6+5=11 and when k=2 we get 12+5=17. so we know that
    6k+5 does produce primes. Now let [itex]X= p_1,p_2,.......p_n [/itex] be the set of all primes
    of the form 6k+5. Now we construct [itex]Y= 6(p_1*p_2*.....*p_n)+5 [/itex]
    Now this new number is bigger than any [itex] p_n [/itex] And lets assume that X is finite. And lets assume 5 is not in X.
    But no [itex] p_n [/itex] divides Y so either Y itself is prime or there is a larger prime of the form 6k+5 that divides it. there are an infinite amount of primes of the form 6k+5.
     
  2. jcsd
  3. May 4, 2013 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi cragar! :smile:
    why?? :confused:

    why can't there be only prime factors of the form 6k + 1 ? :wink:
     
  4. May 4, 2013 #3
    ok i see what you are saying, [itex] Y=6(p_1*p_2*p_3....p_n)+5 [/itex]
    my [itex] p_{n's} [/itex] could be primes of the form 6k+1 , but a prime of the form 6k+1 would not divide
    Y.
     
  5. May 4, 2013 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    no i'm not :confused:
    yes it could :redface:

    (perhaps it may help you to rewrite 6k + 5 as 6K - 1 )
     
  6. May 4, 2013 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, I think you're missing cragar's argument.
    Y is clearly not divisible by 2 or 3. If it is also prime to all primes that are 5 mod 6 then it follows that all of its prime factors are 1 mod 6. But cragar has already shown that the primes 1 mod 6 are closed under multiplication, so it must have a factor that is not 1 mod 6.
    Where the argument in its current form does break down is that Y is always going to be divisible by 5.
     
  7. May 4, 2013 #6
    I dont understand why Y is always divisible by 5. I excluded 5 from my [itex] p_n [/itex]
    and we need to be careful about numbers of the form (6k+1)(6k'+5)=6(6kk'+5k+k')+5 as tiny tim pointed out.
    what I showed is that 6k+5 cant just be composed of factors of the form 6k+1 but it could have factors
    (6k+1)(6k'+5). but I still feel that if we include all the primes of the form 6k+1 and 6k'+5 and called those [itex] p_1,p_2........p_n [/itex] and then look at Y no 6k+1 will divide 5. there is still something i am probably missing, thanks for all the help by the way.
     
    Last edited: May 4, 2013
  8. May 4, 2013 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Ok, you confused me by writing 'let's assume 5 is not in X', which is clearly false, whereas you meant you were redefining X to exclude 5. But the effect is the same - it creates a hole in the argument.
    Why? 6k'+5 would be in X (unless k'=0), and so by construction cannot be a factor of Y. So the only hole in the argument is that Y might be 5 + 6*5*(6k+1)(6k'+1)... = 5*(1+6*(6k+1)(6k'+1)...). OTOH, may be a difficult hole to plug.
     
  9. May 4, 2013 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I don't think it would be hard to plug if cragar had written ##Y=6(p_1*p_2*p_3....p_n)-1##. That is not divisible by 5. The equivalence class 6k+5 is the same as the equivalence class 6k-1 mod 6. They aren't the same mod 5. I really don't think cragar understands the proof very well.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof about 6k+5 producing an infinite amount of primes
  1. Proof about primes. (Replies: 7)

  2. Proof about primes (Replies: 1)

Loading...