I am currently in a number theory class, but we don't have a textbook and even though I have been attending all the lectures we have not solved a problem similar to this in class. We have never proved anything is "not divisible," so the problem is "Prove that $3$ divides $2n^2+1$ if and only if $3$ does not divide $n$." This is what my scratch work has lead me to in one of the directions
WTP: $3\mid2n^2+1\Rightarrow 3\nmid n$
Attempt: So assume for the sake of contradiction that $3\mid2n^2+1$ and $3\mid n$, then $2n^2 +1=3q$ and $n=3d$ for some integers $d$ and $q$. So we have $18d^2 +1 = 3q$. I feel like this may be a contradiction, because we add one to a number that is a multiple of $3$, namely $18d^2$. That is just an intuition I have, but I am not finding anything in my notes that states this as a theorem explicitly.
Please help me and guide me in the right direction.
Best Answer
This is an excellent introduction to proofs question.
You want to prove that $3 \mid 2n^2 + 1$ means that $3 \nmid n$. This is very easily proved through the contrapositive. That is, you might show that $3 \mid n$ means that $3 \nmid 2n^2 + 1$. This direction is easy because you can explicitly divide $2n^2 + 1$ by $3$ and get remainder $1$. $\diamondsuit$