Prove that for all integers $n$ if $3 \mid n^2$, then $3 \mid n$ Prove that for all integers $n$ if $3$ | $n^2$, then $3$ | $n$.
I figured using contrapostive was the best method by using the definition "an integer $k$ is not divisible by 3 if and only if there exists an integer $k$ such that $n=3k+1$ or $n=3k+2$. Also using the definition $a$ divides $b$ written $a$|$b$ if $b=ac$ for some $c$ in integers.
Here it goes:
$$3\nmid n$$
$$3k+1=3n$$
$$\frac{3k+1}{3}=n$$
 A: You don't need to resort to proving the contrapositive; it's possible to prove the statement directly:
If we take as given that $3$ divides (exactly) one of the three consecutive numbers $n-1$, $n$, and $n+1$, then $3$ divides their product, $(n-1)n(n+1)=n^3-n$.  Now if $3$ divides $n^2$, then it also divides $n^3$, and thus it divides the difference, $n^3-(n^3-n)=n$.
A: Presumably you have had the division theorem.
For $n$ and integer there exist integer $k, r$ so that $n = 3k + r$ where $0 \le r < 3$.  So $r = 0, 1$ or $2$.
Can you accept that?
If $r=0$ then $3|n$.  
If $r = 1$ then $n^2 = (3k + 1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$ and $3\not \mid n^2$ and that's a contradiction.
If $r = 2$ then $n^2= (3k + 2)^2 = 9k^2 + 12k + 4 = 3(k^2 + 4k+ 1) + 1$ and $3\not \mid n^2$ and that's a contradiction.
So if $3|n^2$ then the only possibility is $n = 3k$ for some $k$.
A: I believe a simpler way is to use the unique factorization to show that for
$$n = \prod_{i \, = \, 1}^{m} p_i^{a_i} \tag{1}\label{eq1}$$
where the $p_i$ are unique primes, means that
$$n^2 = \prod_{i \, = \, 1}^{m} p_i^{2a_i} \tag{2}\label{eq2}$$
Thus, if $3 \; \vert \; n^2$, then one of the $p_i$ must be $3$, so $3 \; \vert \; n$.
Also, using your suggestion, if $n = 3k + 1$ or $n = 3k + 2$, then $n^2 = 9k^2 + 6k + 1$ or $n^2 = 9k^2 + 12k + 4$. In either case, when dividing by $3$, there is a remainder of $1$, showing that $3$ doesn't divide $n^2$. But, as $3 \; \vert \; n^2$, then $n$ cannot be either of the $2$ forms, so it must be $n = 3k$, giving that $3 \; \vert \;  n$. This is an example of proving what's requested using contrapositive as it shows that if $3 \not{\vert} \; n$, then $3 \not{\vert} \; n^2$.
A: In
If $n \mid a^2 $, what is the largest $m$ for which $m \mid a$?,
I prove this result:
Given 
$n = \prod p_i^{a_i}$,
then the largest $m$
such that
$m | a$ for all $a$
such that
$n | a^2$ is
$m = \prod p_i^{\lceil \frac{a_i}{2}\rceil}$.
If $n$ is a prime,
$3$ in this problems case,
then
$n = 3^1$
so
$m = 3^1$
also.
