# infinitely many primes of the form 6k + 5 and 6K + 1

• Oct 21st 2009, 08:51 AM
MariaJJ
infinitely many primes of the form 6k + 5 and 6K + 1
hey the question is

show that there are infinitely many primes of the form 6k + 5. does the method work for 6k + 1.

suppose there are finite primes of the form 6k + 5
order them such: p(1) < p(2) <....< p(n)
let R = 6(p(1)p(2)...p(n)) + 5
R can't be prime, if it is R > p(n)
R can't be composite as any division will give a remainder of 5
therefore there are infinitely many primes :)

i think there's something not quite right with it and i can't use Dirichlet's Theorem

kudos for any help! :)
• Oct 22nd 2009, 05:25 AM
Media_Man
good work
You have hit the nail on the head. Your proof is correct. Here are some clarifications:

Let \$\displaystyle p_1<p_2<p_3<...<p_n\$ be a finite list of primes of the form \$\displaystyle 6k+5\$. Let \$\displaystyle R=6p_1p_2p_3...p_n+5\$. Since \$\displaystyle R>p_n\$, \$\displaystyle R\$ cannot be prime, so it is composite. When divided by any \$\displaystyle p_i\$, it leaves a remainder \$\displaystyle 5\$, therefore \$\displaystyle R\$ is not divisible by any prime of the form \$\displaystyle 6k+5\$. So \$\displaystyle R\$ must be the product of primes only of the form \$\displaystyle 6k+1\$. But if you take the product of numbers of the form \$\displaystyle 6k+1\$, the product is also of the form \$\displaystyle 6k+1\$. So \$\displaystyle R\$ must leave a remainder \$\displaystyle 1\$ when divided by \$\displaystyle 6\$. But by construction, \$\displaystyle R\$ leaves a remainder \$\displaystyle 5\$ when divided by \$\displaystyle 6\$. We have reached a contradiction, therefore our premise is false: there must be an infinite number of primes of the form \$\displaystyle 6k+5\$.

This argument does not work for the \$\displaystyle 6k+1\$ case. Can you figure out why?