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

I think I need to use the Fundamental Theorem of Arithmetic but that only applies to $a > 1$ so I think I need to do it by cases.

Case 1) $a = 0$.

Case 2) $a = 1$.

Case 3) $a > 1$.

Case 4) $a < 0$.

Cases 1 and 2 are easy. I think Case 4 will follow from Case 3 but I struggle with Case 3.

Case 3) $a > 1$. Then by Fundamental Theorem of Arithmetic, $a$ is equal to a unique product of primes. Then, $a^2$ is a product of those primes squared. Then, because $p$ divides $a^2$, $a^2 = pk$ for some $k$ (an integer). So that product of primes squared equals $pk$. Now how do I argue that one of those primes must be $p$? Once we see that one of those primes is $p$ (i.e. $p$ is a prime factor of $a$), we can say that $p$ divides $a$.

So my questions are: How do I argue that one of those primes must be $p$? Can the proof be done without resorting to four cases?

• How do you have primes defined? One of the most common definitions is that $p$ is a prime integer iff for any integers $x,y$ one has $p\mid xy$ implies $p\mid x$ or $p\mid y$, from which the question is immediately proven noting that $a^2=a\cdot a$. – JMoravitz Sep 10 '16 at 21:35
• This is implied by my question here: math.stackexchange.com/questions/1464864/… – marty cohen Sep 10 '16 at 21:47
• Often proofs can be done with a single, short line that addresses all possible cases. But such proofs can be very difficult for people who are not math professionals to understand. – Mr. Brooks Sep 12 '16 at 21:21

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$

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.

• Your sentence "if $p$ does not divide $a$ then $\text{gcd}(p,a) = 1$ "in the problem's context is a question in its own and needs further explanation. – DeepSea Sep 10 '16 at 21:45

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.

This is a special case of my question (which I answered) here: If $n \mid a^2$, what is the largest $m$ for which $m \mid a$?

In particular, I show that if $p^m | a^2$, then $p^{\lceil m/2 \rceil} | a$. This question is the case $m=1$.

Here is my understanding for what it's worth.

If $a$ is some integer then using the Fundamental Theorem of Arithmetic like you mentioned $a$ can be written as a product of prime numbers. Let's say $a=bcd$ where $b$ , $c$ and $d$ are prime numbers. From this we can see that $a^2=bbccdd$. If $p$ divides evenly into $a^2$ then $p$ must be equal to either one of $b$ , $c$ or $d$. It can't be a product of any of them as it is prime itself. Let's say $p=c$. We can see that $c$ is also a factor of $a$. Whichever factor of $a^2$ that equals $p$ also exists in $a$.