Prove by contradiction that if $n^3$ is a multiple of $3$, then $n$ is a multiple of $3$ Problem statement:
Using proof by contradiction, prove that if $n^3$ is a multiple of $3$ , then $n$ is a multiple of $3.$
Attempt 1:
Assume that there is exist $n$ which  is a multiple of $3$ such that $n^3$ is not a multiple of $3.$
Then $n = 3k $ , $n^3 = 27 k^3 $ which a multiple of $3$, which contradicts the assumption that $n^3$ is a multiple of $3.$
Attempt 2:
Assume that there exist $n^3$ which is a multiple of $3$ such that $n$ is not a multiple of $3.$
Then $n = k+ 1 $ or $n= k+2.$
Then $n^3 = k^3 + 3k^2 + 3k + 1$
or $n^3 = k^3 + 6 k^2 + 12 k + 8.$
Both cases contradict the assumption that $n^3 $ is a multiple of $3.$
Which solution is correct ? Or do both work ?

If $P,Q$ are statements then $P \implies Q$ is same as $ \neg Q \implies \neg P $.
Here $P : n^3$ is a multiple of $3$ and $Q: n$ is a multiple of $3$.
So if you want to prove it by contradiction you have to assume that $n^3$ is multiple of $3$ but not $n$ and then get a contradiction.
You can  do this by noting that every number is in the form $3k, 3k+1$ or $3k +2$. If $n$ is a not a multiple of $3$ then it has to be in the form of $3k+1$ or $3k +2$
