# Infinitely many composite numbers

1. Feb 22, 2013

### bonfire09

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. Feb 22, 2013

### SqueeSpleen

You can do it showing a constructive way to finding such numbers.

Last edited: Feb 22, 2013
3. Feb 22, 2013

### bonfire09

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.

4. Feb 22, 2013

### SqueeSpleen

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
5. Feb 22, 2013

### bonfire09

I was thinking something with congruences.

6. Feb 22, 2013

### SqueeSpleen

I think it can work, but it can be done in a simplier way.

7. Feb 22, 2013

### Dick

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.

8. Feb 22, 2013

### bonfire09

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.

9. Feb 22, 2013

### Dick

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"?

10. Feb 22, 2013

### bonfire09

Oh you mean like (x+1)^2? That might work since that is always composite.

11. Feb 22, 2013

### Dick

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
12. Feb 22, 2013

### bonfire09

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
13. Feb 22, 2013

### Dick

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?

14. Feb 23, 2013

### SqueeSpleen

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