1. Limited time only! Sign up for a free 30min personal 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!

Infinitely many composite numbers

  1. Feb 22, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove that there are infinitely many n such that 6n+1 and 6n-1 are both composite.


    2. Relevant equations



    3. The attempt at a solution
    I have no idea where to start. I was thinking that this must be some form of Euclid's theorem but I don't know how to work that into this proof.
     
  2. jcsd
  3. Feb 22, 2013 #2
    You can do it showing a constructive way to finding such numbers.
     
    Last edited: Feb 22, 2013
  4. Feb 22, 2013 #3
    So basically I should just generate a sequence for each form and see if I can see a pattern? Then try to prove it? I was thinking of using proof by contradiction, but I'm getting anywhere yet.
     
  5. Feb 22, 2013 #4
    My suggestion is first to find a number with those properties. Then, think what you can do to use it to generate numbers with the same property.
    Contradiction seems to be a difficult way to me.
     
    Last edited: Feb 22, 2013
  6. Feb 22, 2013 #5
    I was thinking something with congruences.
     
  7. Feb 22, 2013 #6
    I think it can work, but it can be done in a simplier way.
     
  8. Feb 22, 2013 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I think you should give bonfire9 a hint, SqueeSpleen. There's nothing wrong with that. Make it a 'little' one. Ok, looks like you're gone. I'll give one. x^2-1 is never prime. Why not? That's a hint.
     
  9. Feb 22, 2013 #8
    Ok im creating a list of the numbers of when they are both composite
    n=24,n=31,n=34,n=36,n=41,n=48,... This is what I got but I don't see a pattern Oh so wait (x+1)(x-1)=x^2-1. That is what is similar to (6x-1)(6x+1)=36x^2-1.
     
  10. Feb 22, 2013 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, but that's not quite what I'm getting at. Sure x^2-1 is never prime for the reason you gave. That means 6^2-1 is composite. That doesn't help for the 6^2+1 part. In fact, it isn't composite. Can you think of some other polynomial factorizations like x^2-1 where instead of "-1" you have "+1"?
     
  11. Feb 22, 2013 #10
    Oh you mean like (x+1)^2? That might work since that is always composite.
     
  12. Feb 22, 2013 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Always composite, yes. But not useful in this problem, is it? x^2-1 is. Isn't it? That can prove 6n-1 is composite if 6n is a perfect square. There's an infinite number of those. You can do something with the 6n+1 if you think harder about other polynomials that factor. Think, think, think. It could be really easy.
     
    Last edited: Feb 22, 2013
  13. Feb 22, 2013 #12
    Multiply by 6x+1 and 6x-1. Then you get (6x+1)2(6x-1)2 That should ensure its always composite. Yeah Im going to think about it more. I'll reply back when I have an answer. I'll take it from here.
     
    Last edited: Feb 22, 2013
  14. Feb 22, 2013 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Multiplying almost any two numbers gives you a composite. You don't want to prove the product is composite, you want to prove the two numbers you are multiplying are composite. One more hint. And this might be too many. When is x^3+1 prime?
     
  15. Feb 23, 2013 #14
    Thanks for giving him the hint, I'm not very good giving the hints without spoiling the complete solution :P
    My hint is to solve in a different way that Dick solved it.
    Here's my hint:
    My first number was 6*20=120, 120=7*17+1 and 121=11*11-1
    What can I add to 120 to know I'll have a number with similar properties?
     
    Last edited: Feb 23, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Infinitely many composite numbers
Loading...