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

1 Answer 1

Reset to default
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$ Commented 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$ Commented Jan 29, 2014 at 23:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.