elementary number theory - 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$.

Answer

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.