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

6 comments:

  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

    ReplyDelete
  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.

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

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

    ReplyDelete
  5. Good call. Oh well.

    ReplyDelete