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

1. May 4, 2013

### cragar

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 $X= p_1,p_2,.......p_n$ be the set of all primes
of the form 6k+5. Now we construct $Y= 6(p_1*p_2*.....*p_n)+5$
Now this new number is bigger than any $p_n$ And lets assume that X is finite. And lets assume 5 is not in X.
But no $p_n$ 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. May 4, 2013

### tiny-tim

hi cragar!
why??

why can't there be only prime factors of the form 6k + 1 ?

3. May 4, 2013

### cragar

ok i see what you are saying, $Y=6(p_1*p_2*p_3....p_n)+5$
my $p_{n's}$ could be primes of the form 6k+1 , but a prime of the form 6k+1 would not divide
Y.

4. May 4, 2013

### tiny-tim

no i'm not
yes it could

(perhaps it may help you to rewrite 6k + 5 as 6K - 1 )

5. May 4, 2013

### haruspex

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.

6. May 4, 2013

### cragar

I dont understand why Y is always divisible by 5. I excluded 5 from my $p_n$
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 $p_1,p_2........p_n$ 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
7. May 4, 2013

### haruspex

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.

8. May 4, 2013

### Dick

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.