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.

  • 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 '14 at 22:33
  • $\begingroup$ @abiessu Why subtract six? $\endgroup$ – Warz Jan 29 '14 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 '14 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 '14 at 22:38
  • $\begingroup$ @abiessu i've edited my original answer - is this what you're getting at? $\endgroup$ – 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$.

  • $\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 '14 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$ – Barry Cipra Jan 29 '14 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.