Showing that a number is not divisible by another.

Question

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.

Answer 1

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$

Answer 2

I think your intuition is on the right track.

$$18d^2 +1 = 3q$$

$$q=6d^2 + \frac{1}{3}$$

$$q-6d^2=\frac{1}{3}$$

I believe it's correct to say here that since the set of Integers is closed under addition and multiplication, you have your desired contradiction.