Say $n$ is a natural number and $n^2$ is a multiple of 5. Does that mean $n$ is a multiple of 5?

This seems to be true. If we look at squares:

\[
\begin{align*}
2^2 &= 4 & 3^2 &= 9 & 4^2 &= 16 & \mathbf{5^2} &\mathbf= \mathbf{25} \\
6^2 &= 36 & 7^2 &= 49 & 8^2 &= 64 & 9^2 &= 81 \\
\mathbf{ {10}^2 }&\mathbf= \mathbf{100} & {11}^2 &= 121 & {12}^2 &= 144 & {13}^2 &= 169 \\
{14}^2 &= 196 & \mathbf{ {15}^2 }&\mathbf= \mathbf{225} & {16}^2 &= 256 & {17}^2 &= 289 \\
{18}^2 &= 324 & {19}^2 &= 361 & \mathbf{ {20}^2 }&\mathbf= \mathbf{400} & {21}^2 &= 441\\
\end{align*}
\]

Seems to be that $n^2$ is a multiple of 5 only when $n$ is. Can we prove it?

If $n^2$ is a multiple of 5, then $n^2 = 5k$ for some $k \in \mathbb{N}$. Then $n = 5k/n = 5(k/n)$, which means $n$ is a multiple of 5 as long as $k/n$ is an integer… which is true if $k$ is a multiple of $n$. Is $k$ a multiple of $n$?

Well, $k = n^2/5 = n(n/5)$, which means $k$ is a multiple of $n$ if $n$ is a multiple of 5… ah, we’re in a loop here. Let’s try something else.

Maybe we need to use something specific about 5. Is this property true for all numbers? What about 4: is $n$ a multiple of 4 whenever $n^2$ is?

\[
\begin{align*}
\mathbf{2^2} &\mathbf= \mathbf{4} & 3^2 &= 9 & \mathbf{4^2} &\mathbf= \mathbf{16} & 5^2 &= 25 \\
\mathbf{6^2} &\mathbf= \mathbf{36} & 7^2 &= 49 & \mathbf{8^2} &\mathbf= \mathbf{64} & 9^2 &= 81 \\
\mathbf{ {10}^2} &\mathbf= \mathbf{100} & {11}^2 &= 121 & \mathbf{ {12}^2} &\mathbf= \mathbf{144} & {13}^2 &= 169 \\
\end{align*}
\]

No! 4, 36, and 100 are multiples of 4, but 2, 6, and 10 are not multiples of 4.

There must be something different about 5 that makes this work for it. 5 is prime… can that help?

The fundamental theorem of arithmetic is often handy when dealing with primes. Let’s represent $n$ as its prime factorization:

\[
n = p_1p_2\cdots p_n
\]

Then:

\[
n^2 = p_1^2p_2^2\cdots p_n^2
\]

If $n^2$ is a multiple of 5, then 5 must be in $n^2$’s prime factorization. Which means 5 must be one of the primes $p_i$, which in turn means that $n$ itself must also have $5$ as a factor. Woohoo!

So we’ve proved this is true for 5. And, clearly, it’s true for any other
prime number. We know it’s not true for 4. Is this true *only* for primes?
Let’s look at 6:

\[
\begin{align*}
2^2 &= 4 & 3^2 &= 9 & 4^2 &= 16 & {5^2} &= {25} \\
\mathbf{6^2} &\mathbf= \mathbf{36} & 7^2 &= 49 & 8^2 &= 64 & 9^2 &= 81 \\
{10}^2 &= {100} & {11}^2 &= 121 & \mathbf{12}^2 &\mathbf= \mathbf{144} & {13}^2 &= 169 \\
{14}^2 &= 196 & {15}^2 &= {225} & {16}^2 &= 256 & {17}^2 &= 289 \\
\mathbf{18}^2 &\mathbf= \mathbf{324} & {19}^2 &= 361 & { {20}^2 }&= {400} & {21}^2 &= 441\\
\end{align*}
\]

Hm… seems like this actually might be true for 6, even though 6 isn’t prime. Can we prove it? It turns out we can make a pretty similar argument:

If $n^2 = p_1^2p_2^2\cdots p_n^2$ is a multiple of 6, 6 *won’t* be any of
the $p_i$ (because 6 isn’t a prime). But 6 = 2*3, which means one of the
$p_i$ must be 2 and another of the $p_i$ must be 3.

In case it isn’t clear why: if $m$ is a multiple of 6, then $m = 6k = 2\cdot3\cdot k$. We can prime-factorize $k = q_1q_2\cdots q_n$, which means $m = 2\cdot3\cdot q_1\cdot\cdots\cdot q_n$.

This means $n$’s prime factorization contains 2 and 3, which means $n$ is a multiple of 6. QED

So hang on… since every number has a prime factorization, can’t we make this argument for any number? What goes wrong with 4?

If $n^2 = p_1^2p_2^2\cdots p_n^2$ is a multiple of 4, since 4 = 2*2, one
of the $p_i$ must be 2 and another of the $p_i$ must be… ah, 2
again. So we can’t actually prove that $n$ is a multiple of 4, but we
*can* prove that it’s a multiple of 2.

4 happens to be a perfect square, but we’ll actually run into this problem for other numbers too. 12 = 2*2*3. If $n^2 = p_1^2p_2^2\cdots p_n^2$ is a multiple of 12, one of the $p_i$ is 2, one of the $p_i$ is 2 (again), and one of the $p_i$ is 3. So all we know for sure is that $n$ is a multiple of 2*3 = 6.

So it’s clear that this property holds for any $k$ that doesn’t have any repeats in its prime-factorization. These numbers are called square-free.

But even if our number isn’t square-free (like 4, or 12), we can still say
something, which is that $n$ is a multiple of the number that you get when
you get rid of all the duplicates in $k$’s prime factorization. The term
for this is an integer’s
*radical*:

\[
\begin{align*}
\operatorname{rad}({4}) &= \operatorname{rad}({2^2}) = 2 \\
\operatorname{rad}({5}) &= 5 \\
\operatorname{rad}({6}) &= \operatorname{rad}({2\cdot3}) = 2\cdot3 = 6 \\
\operatorname{rad}({12}) &= \operatorname{rad}({2^23}) = 2\cdot3 = 6 \\
\end{align*}
\]

So the most general thing we can say is: if $n^2$ is a multiple of $k$, $n$ is a multiple of $\operatorname{rad}(k)$.

Inspired by Putnam 2017 A1.

*- alec, May 23, 2020*