Is this proof about primes correct?

113 Views Asked by At

We were shown a proof today that supposedy showed that all primes are of the from $6n\pm1$. While I have no issues with this conclusion, and have found valid proofs online, I was unsure as to the validity of the approach given:

To prove by contradiction, we assume that there are primes not of the sequence $6n\pm1$. Take the sequence $6n+3$. Since it contains no primes, we have arrived at a contradiction, therefore the premise is true.

I've given above (restated in my own words) the proof given today. The main issue I have with it is the binary classification of the sequence $6n\pm1$ and all other sequences, and the idea that it is sufficient to prove that $1$ sequence ($6n+3$) contains no primes, to show that all primes are of the sequence $6n\pm1$.

Is my intuition on this correct? Or is this a valid proof? If so, why?

EDIT: Just to clarify, all of the above applies to primes $> 3$

3

There are 3 best solutions below

0
On

An odd number $>3$ can be written in exactly one of the forms $6n-1$, $6n+1$, or $6n+3$. Primes $>3$ are odd, so if it is not of the form $6n \pm 1$, it must be of the form $6n+3$.

0
On

I would say that the proof is not complete.

He also needs to show that we cannot have prime of the form of $6n$, $6n+2=2(3n+1)$, $6n+4=2(3n+2)$

2
On

That is not a proof, because you are not considering all the cases here.

If you want to prove your statement by contradiction you have consider the cases :

$$6n,$$

$$6n+2,$$

$$6n+3,$$

$$6n+4.$$

This is not much more difficult thant the cases $6n+3$ though (it is the same method each time) but you have to consider those cases anyway.