Prove that if $p$ is a prime, $a$ is an integer, and $p$ divides $a^2$, then $p$ divides $a$.

Using prime factorization of $a = p_1^{n_1}p_2^{n_2}\cdots p_m^{n_m}$ where $p_j$'s are distinct primes, and $n_j$'s are natural numbers. Thus $p\mid a^2 = p_1^{2n_1}p_2^{2n_2}\cdots p_m^{2n_m}$. Since $p$ is a prime $p = p_k$, for some $1 \le k \le m$, and this implies $p \mid p_1^{n_1}p_2^{n_2}\cdots p_m^{n_m} = a$

Assume that $p \nmid a$. Then, $a=p \cdot q +r$ for some $r >0$, s.t. $r \neq 0 (modp) $.

Since, ${p \mid a^2 } \Rightarrow {a^2 \equiv 0 (mod p)}$

So, $a^2=(p \cdot q +r)^2=p^2 q^2+2pqr+r^2 \equiv r^2 (modp)\neq 0 (modp) \Rightarrow p \nmid a^2$ Contradiction.

If $p$ does not divide $a$ then $\gcd(p,a)=1.$ By Euclidean Algorithm (or Bezout) there are integers $x$ and $y$ so that $px+ay = 1$. Multiply by $a$ to get $apx+a^2y = a.$ Since $p$ divides the left side, it must divide the right, contradiction.