Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
"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 at 22:33
    
@abiessu Why subtract six? –  Warz Jan 29 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 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 at 22:38
    
@abiessu i've edited my original answer - is this what you're getting at? –  Warz Jan 29 at 22:46

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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? –  Warz Jan 29 at 23:26
    
@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 at 23:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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