## Tuesday, May 8, 2007

### 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$.

1. This actually has nothing to do with your question, but i thought it was pretty interesting:

Isn't nonexistence or existence only as an idea still a form of existence?

Which analogy is better?:

existence:nonexistence
1 : -1

existence:nonexistence
1 : 0

2. 1 : 0.

Nonexistence is the absence of existence. And yes, the concept of nonexistence is a form of existence, but who claimed otherwise? Nonexistence does not have to describe itself.

3. 4. Hey! You should've gone to bed.

5. Looking at this, it appears obvious that n = 1 is also a solution

6. Good call. Oh well.