# Elementary Divisibility Proof

Q: $$n\in\mathbb{Z}$$. Prove that $$3 | 2n^2 +1$$ iff $$3\nmid n$$.

I began by assuming not true. Then $$3|n$$ implies $$n=3k$$ where $$k\in\mathbb{Z}$$.

$$3 | 2(3k)^2 +1$$ $$\rightarrow$$ $$3 | 2(9k^2)+1$$ $$\rightarrow$$ $$3 | 18k^2 +1$$.

$$3 | 3(6k^2 + \dfrac{1}{3})$$ but $$6k^2 + \dfrac{1}{3}$$ is not an integer. Contradiction.

Is this proof valid?

• The thing you are trying to prove (at least what you've stated) is not true. Feb 16 at 15:17
• There is a typo somewhere, we have $3\mid 2n^2+1$ iff $3\nmid n$ instead. Feb 16 at 15:18
• Fixed it @paw88789 Feb 16 at 15:21
• The statement you are asked to prove asserts "if and only if". Your hypothetical proof by contradiction will still need a two way argument. Better strategy: there are only three cases modulo $3$. Check each one separately. Feb 16 at 15:24
• No. You need to check the cases $n \equiv 0,1,2 \pmod{3}$. You can do a lot less algebra if you do the arithmetic modulo $3$ rather than with the forms $3k+r$. Then you see $2^2 \equiv 1$ immediately. Feb 16 at 15:39

Your proof is valid, but here's an easier way to see and write this- $$3|n\iff 3|n^2\iff 3|2n^2\iff 3\nmid 2n^2+1$$ The idea is just to realise that $$n$$ cannot divide both $$f(n)$$ and $$f(n)+1$$.
$$n=3k+1\implies 2n^2+1=2(3k^\prime)+2+1\equiv 0 \;(\operatorname{mod }3)$$ $$n=3k+2\implies 2n^2+1=2(3k^\prime)+2.2^2+1\equiv 0\;(\operatorname{mod }3)$$
• The last assertion in this answer requires more work. It's not true in general that if $3$ does not divide $A+1$ then it divides $A$. Feb 16 at 15:27