Dear Uncle Colin,

If you know all of the factors of $n$, can you use that to find all of the factors of $n^2$? For example, I know that 6 has factors 1, 2, 3 and 6. Its square, 36, has the same factors, as well as 4, 9, 12, 18 and 36, but I don’t see an easy way to find them all – just squaring the original factors misses 12 and 18, and looping over all of the possibilities seems inefficient, especially for larger numbers.

- Something Quite Upsetting About Recursively Enumerating Divisors

Hi, SQUARED - and thank you for your message!

Sadly, I don’t think there’s a quick and simple way to use the factors directly, other than (as you say) looping through them and checking.

However, there is a method to get them all from the prime factorisation of $n$. In your example, $n=2\times3$, so $n^2=2^2\times3^2$. You can list all of the factors of $36$ by listing every number of the form $2^i 3^j$, with $0\le i\le 2$ and $0\le j\le2$.

Here, you’d get:

  |   | $i=0$ | $i=1$ | $i=2$ | | $j=0$ | 1 | 2 | 4 | | $j=1$ | 3 | 6 | 12 | | $j=2$ | 9 | 18 |36 |

… which all drops out nicely.

In general, if $n = p_1^{f_1}p_2^{f_2}p_3^{f_3}…p_k^{f_k}$, then $n^2$ has all possible factors of the form $p_1^{i_1}p_2^{i_2}p_3^{i_3}…p_k^{i_k}$, where $0\le i_m\le f_m$ for all $m=1,2,…,k$. In all, you’ll have $(f_1+1)(f_2+1)…(f_k+1)$ factors.

Hope that helps!

- Uncle Colin