# Modified Euclid's proof of infinite primes

Q. Alternate the proof for Euclid's infinite number of primes to show there are infinitely prime numbers of the form $6n-1$ where n is an integer.

my attempt,

suppose by contradiction there are finitely many primes, i.e. suppose $p_1 = 6(1) -1$, $p_2 = 6(2) - 1$...$p_n = 6n -1$ are all prime

If we take the product of all the primes $p_1...p_n$ we'll end up with $p_1...p_n = 6m - 1$ or $6n+1$, hence if the product is $6m - 1$ let $N_1 = p_1....p_n - 6 = 6(m-1) - 1 = 6k - 1$ By the prime factorisation theorem, there exists a prime factor q

$p_i$ does not divide $N_1$ and $q \not = p_i$ so q divides $N_1$ and is of the form $6k-1$

if $p_1...p_n = 6m + 1$ let $N_2 = p_1...p_n - 2$ and use a similar argument

is this the right approach?

edit: on second thoughts, wouldn't letting $N = 6p_1...p_n - 1$ work? As no $p_i$ divides N (as you have a remainder of -1) and any divisor of N (q), will be in the form of $6n-1$ as $p_1...p_n$ is just some integer.

• "Multiply all the primes of the form $6n-1$ together; if the result is $6m+1$ then subtract $2$, else subtract $6$. ..." – abiessu Jan 29 '14 at 22:33
• @abiessu Why subtract six? – Warz Jan 29 '14 at 22:36
• Both $2$ and $6$ are relatively prime to all integers of the form $6n-1$. If you multiplied all the numbers of the form $6n-1$ together, you would get a number $6m\pm 1$; if the number is not of the form $6m+1$ then it is of the form $6m-1$ and so subtracting $6$ makes it relatively prime to all its prior factors. Of course, if it is claimed that $5$ is the only such prime, then maybe it would be better to add $6$ instead... – abiessu Jan 29 '14 at 22:38
• $q$ does not necessarily have a prime factor of the form $6n-1$, for example $5\times 11 + 1 = 56 = 2^3\times 7$. You need to find something else. – fkraiem Jan 29 '14 at 22:38
• @abiessu i've edited my original answer - is this what you're getting at? – Warz Jan 29 '14 at 22:46

Your "second thoughts" idea is basically correct, but what you need to say is that not all the prime factors of $N=6p_1\cdots p_n-1$ can be of the form $6k+1$ (since the product of such primes is still of the form $6k+1$). The number $N$ can have some divisors of the form $6k+1$. For example $N=6\cdot5\cdot11-1=329=7\cdot47$.
• @Warz, the key point is that every number of the form $6k-1$ is necessarily divisible by some prime of the same form. You seemed to be saying that all the prime divisors of such a number would have the same form. – Barry Cipra Jan 29 '14 at 23:51