A Square of Divisors. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (1999 Canada - #3) Determine all positive integers $ n > 1 $ with the property that $n = (d(n))^2$. Here $d(n)$ denotes the number of positive divisors of $n$.

Solution: So, testing some small numbers yields $ n = 9 $ as a solution. We claim that this is the only such solution.

Clearly, since $ n $ is a square, we can use a variant of the usual prime decomposition and say that $ n = p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} $.

Furthermore, again since $ n $ is a square, we know

$ d(n) = (2e_1+1)(2e_2+1) \cdots (2e_k+1) $

is odd, so $ n = (d(n))^2 $ must be odd as well, i.e. $ 2 $ is not one of the $ p_i $. Then we use the equation given to us to get

$ p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} = (2e_1+1)^2(2e_2+1)^2 \cdots (2e_k+1)^2 $

$ p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} = (2e_1+1)(2e_2+1) \cdots (2e_k+1) $.

Note, however, that by Bernoulli's Inequality (overkill, I know) we have for $ i = 1, 2, \ldots, k $

$ (1+(p_i-1))^{e_i} \ge 1+(p_i-1)e_i \ge 2e_i+1 $

with equality iff $ p_i = 3 $ and $ e_i = 1 $. So

$ p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \ge (2e_1+1)(2e_2+1) \cdots (2e_k+1) $.

Since we want equality, we must have $ p_i = 3 $ and $ e_i = 1 $ for all $ i $. But since the primes are supposed to be distinct we can have exactly one prime so that $ n = 3^2 = 9 $ is the only solution. QED.

--------------------

Comment: Another one of those problems that you kind of look at the result and you're like huh, that's interesting. But anyway, just throwing in some weak inequalities led to a pretty straightforward solution. As long as you know how to find the number of divisors of a positive integer it isn't too much of a stretch to figure the rest out, though it make take some time to get in the right direction since the problem is quite open-ended.

--------------------

Practice Problem: (1999 Canada - #4) Suppose $a_1,a_2,\cdots,a_8$ are eight distinct integers from $\{1,2,\ldots,16,17\}$. Show that there is an integer $k > 0$ such that the equation $a_i - a_j = k$ has at least three different solutions. Also, find a specific set of $7$ distinct integers from $\{1,2,\ldots,16,17\}$ such that the equation $a_i - a_j = k$ does not have three distinct solutions for any $k > 0$.