0
$\begingroup$

CONTEXT: Challenge question set by uni lecturer for discrete mathematics course

Question: Prove the following statement is true using proof by contradiction:

For all positive integers $x$, if $x$, $x+2$ and $x+4$ are all prime, then $x=3$.

I know I'd do this by trying to prove the negation of the statement, but then failing to do so and hence 'contradicting' myself.

I've also found the negation to be that there exists a positive prime integer $x$ such that 𝑥+2 and 𝑥+4 are prime, but $x≠3$

I'm stuck at the part of the proof where you show that the negation is false.

$\endgroup$
  • 1
    $\begingroup$ Hint: precisely one of $x$, $x+1$, and $x+2$ MUST be divisible by $3$ $\endgroup$ – Brian Mar 14 at 14:31
  • $\begingroup$ @Brian Can you please explain why this is the case? $\endgroup$ – Ruby Pa Mar 14 at 14:43
1
$\begingroup$

Hint: One of $x, x+2, x+4$ must be divisible by $3$.

$\endgroup$
  • $\begingroup$ Can you please explain why this is the case? $\endgroup$ – Ruby Pa Mar 14 at 14:42
  • $\begingroup$ These three integers have mutually distinct residues divided by 3. So, (precisely) one of them should be a multiple of 3. I hope this makes it clear. $\endgroup$ – Song Mar 14 at 14:46
0
$\begingroup$

Assume not, so $\exists x$ positive integer s.t. $x, x+2, x+4$ prime but $x\neq3$.

But we can look at the numbers modulo 3, and realize that there are 3 possiblilities:

1) $x\equiv 0 (mod 3)$. So $x+2\equiv 2 (mod 3)$ and $x+4\equiv 1 (mod 3)$

2) $x\equiv 1 (mod 3)$. So $x+2\equiv 0 (mod 3)$ and $x+4\equiv 2 (mod 3)$

3) $x\equiv 2 (mod 3)$. So $x+2\equiv 1 (mod 3)$ and $x+4\equiv 0 (mod 3)$

In any event, one of the 3 numbers must be divisble by 3, which means it is not prime (unless it is equal to 3). Which is only possible if $x=3$

$\endgroup$

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.