Invalid Proof involving Divisors? Let $x, y \in \mathbb{Z}$. If $x \mid y^{2}$ then $x \mid y$. One counter example would be to let $x = 16$ and $y = 4$. We know that $16 \mid 16$, but $16 \nmid 4$. 
My question is what is wrong with the following proof. Lets show the contrapositive, $x \nmid y$, then $x \nmid y^2$.
$x \nmid y$ implies that $y = cx + 1$ where $c \in \mathbb{Z}$. Then $y^{2} = c^{2}x^{2} + 2cx + 1 = x(c^{2}x + 2c) + 1$ and we know that $c^{2}x + 2c$ is an integer. Since $y^{2}$ is in the same form as $y$, we can conclude that $x \nmid y$.  
 A: Your first statement, that $x\nmid y$ implies $y=cx+1$ for some $c\in\mathbb{Z}$, is false.
It's a good idea in these situations (where you have a counterexample, but also what seems like a valid proof) to plug in the counterexample into each step of your supposed proof, and see where a false statement first appears. Using $x=16$ and $y=4$, we see that even though $16\nmid 4$, we cannot have $16=4c+1$ for any $c\in\mathbb{Z}$; the left side is always odd, and in fact always congruent to 1 modulo 4 (essentially by definition), while 16 is congruent to 0 modulo 4.
A: Remember that instead of $y=cx+1$, we have $\exists c,r \in \mathbb{Z}: y = cx+r$ where $0\leq r < x$. Note that in this specific case, we have $r > 0$.
A: An integer $\rm\:q\ne 0\:$ satisfies $\rm\:q\ |\ n^2\ \Rightarrow\ q\ |\ n\ $ for all integers $\rm\:n\:$ iff $\rm\:q\:$ is squarefree, i.e. $\rm\:q\:$ is not divisible by any square $> 1$. Below are some equivalent characterizations of squarefree integers (for the proofs see here).
THEOREM $\ $ Let $\rm\ 0 \ne q\in \mathbb Z\:.\ $ The following are equivalent. 
$(1)\rm\quad\:\ \ n^2\ |\ q\ \Rightarrow\ n\ |\ 1\qquad\qquad\!$ for all $\rm\ n\in \mathbb Z $
$(2)\rm\quad\:\ \  n^2\ |\ q\:m^2 \Rightarrow\ n\ |\ m\qquad\  $ for all $\rm\:\ n,m\in \mathbb Z$
$(3)\rm\qquad\  q\ |\ n^2\ \Rightarrow\ q\ |\ n\qquad\quad\ $ for all $\rm\:\ n\in \mathbb Z $
$(4)\rm\qquad\ q\ |\ n^k\ \Rightarrow\ q\ |\ n\qquad\quad\ $ for all $\rm\:\ n\in \mathbb Z\:,\ k\in \mathbb N $
$(5)\rm\quad\:\ \: q^q\ |\ n^n\ \Rightarrow\ q\ |\ n\qquad\quad\ $ for all $\rm\:\ n\in \mathbb N\:,\ $ for $\rm\ q > 0 $
