2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ "Multiply all the primes of the form $6n-1$ together; if the result is $6m+1$ then subtract $2$, else subtract $6$. ..." $\endgroup$
    – abiessu
    Jan 29, 2014 at 22:33
  • $\begingroup$ @abiessu Why subtract six? $\endgroup$
    – Warz
    Jan 29, 2014 at 22:36
  • $\begingroup$ 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... $\endgroup$
    – abiessu
    Jan 29, 2014 at 22:38
  • $\begingroup$ $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. $\endgroup$
    – fkraiem
    Jan 29, 2014 at 22:38
  • $\begingroup$ @abiessu i've edited my original answer - is this what you're getting at? $\endgroup$
    – Warz
    Jan 29, 2014 at 22:46

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ sorry, I don't understand why I need to say that. Could you elaborate on why you're using prime numbers in the form of 6k + 1? $\endgroup$
    – Warz
    Jan 29, 2014 at 23:26
  • $\begingroup$ @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. $\endgroup$ Jan 29, 2014 at 23:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .