# Under what conditions does an integer dividing the square of n imply that the integer must divide n?

Under what conditions does an integer dividing the square of n imply that the integer must divide n?

I believe it's that the integer must be prime, but maybe not...I can see counterexamples for certain composites, like 12 divides the square of 6, but 12 does not divide 6, but I it seems like if 6 (also a composite) divides the square of a number, it will necessarily divide the number. What's different about 6 and 12? Is it that 6's prime factorization has an only odd powers?

I ask because of a response under a question about proving that if n squared is even, then n is even. One proof says essentially, "given that 2 divides square of n, since 2 is prime, 2 must divide n," but I'm not seeing so much the "since 2 is prime" part...

• Note on your reason for asking: If a prime $p$ divides $n^2$, then $p$ must indeed divide $n$. To see this look at the prime decomposition of $n$, $n=p_1^{m_1}\cdot p_2^{m_2}\ldots p_k^{m_k}$ where $p_1\ldots p_k$ are primes. Then $n^2=p_1^{2m_1}\cdot p_2^{2m_2}\ldots p_k^{2m_k}$. Note that there are no new prime factors. If $p$ is prime and divides $n^2$, then $p$ must be one of those prime-factors, $p=p_j$ for some $j$. And that $p_j$ will also be a prime-factor of $n$ since the prime-factors of $n$ and $n^2$ are the same. Thus $p$ must divide $n$ if it is prime and divides $n^2$. – Shinja Mar 12 '17 at 21:11

The inverse is easier to understand: under what conditions does $m$ divide $n^2$ but fail to divide $n$? In other words, when does the prime factorization of $m$ fail to show up in $n$ when it shows up in $n^2$? For this to happen $m$ must be composite (because if $n$ and $n^2$ have the same unique prime factors-- if $m$ equals one of them, it'll show up in both). Hopefully this helps to explain the bit about "because 2 is prime. . .".