Proving that a natural number is divisible by $3$ I am trying to show that $n^2 \bmod 3 = 0$ implies $n \bmod 3 = 0$.
This is a part a calculus course and I don't know anything about numbers theory. Any ideas how it can be done? Thanks!

The natural way to think about the problem is that since $n^2$ is divisible by 3, hence prime factorization of $n^2$ contains at least one 3 in it(since 3 is a prime number). If so is the case, then prime factorization of $n$ must contains 3 in it. 
