Originally Posted by

**novice** For any integer $\displaystyle a$ and $\displaystyle n, n | a^2$ if and only if $\displaystyle n | a.$

Let P: $\displaystyle n | a^2 $

and $\displaystyle Q: n | a$.

I have no trouble proving $\displaystyle Q \Rightarrow P$.

I have trouble with $\displaystyle \sim Q \Rightarrow P$.

I am doing it by showing that if $\displaystyle n \not | a$, then $\displaystyle a \not = ny $ or equivalently,

$\displaystyle a = n y + c$, where $\displaystyle y, c \in \mathbb{Z}$ and 1$\displaystyle \leq c < n$. It doesn't look too good.

How do you prove $\displaystyle P \Rightarrow Q$?

For $\displaystyle P \Rightarrow Q$ is it okay to prove $\displaystyle Q \Rightarrow \sim P$ to get the contradiction?