2004 IMO Shortlist Problems/N1

Problem

(Belarus) Let $\displaystyle \tau(n)$ denote the number of positive divisors of the positive integer $\displaystyle n$ . Prove that there exist infinitely many positive integers $\displaystyle a$ such that the equation

$\displaystyle \tau(an) = n$

does not have a positive solution $\displaystyle n$ .

This was also a problem on the 2005 TSTs for Australia and Germany.

Solutions

Solution 1

If $\displaystyle \tau(an) = n$ , then $\frac{an}{\tau(an)} = a$ , i.e., there exists $\displaystyle m$ such that $\frac{m}{\tau(m)} = a$ . The converse is also true, since $\displaystyle \tau(m)a = m$ (i.e., $a \mid m$ .) Thus the existance of $\displaystyle n$ such that $\displaystyle \tau(an) = n$ is equivalent to the existance of $\displaystyle m$ such that $\displaystyle \frac{m}{\tau(m)} = a$ .

Note that for any integer $\displaystyle m$ has at most $\sqrt{m}$ divisors less than or equal to $\sqrt{m}$ , and for each divisor $d > \sqrt{n}$ , a divisor $\frac{n}{d} < \sqrt{n}$ . Hence we obtain the inequality

${} \tau(n) \le 2\sqrt{n} \qquad (*)$ .

It is sufficient to prove that for prime $\displaystyle p \ge 5$ , the equation $\frac{m}{\tau(m)} = p^{p-1}$ has no solutions. Assume the contrary. Clearly, if $\displaystyle m$ is a solution, then $p^{p-1} \mid m$ , so let $\displaystyle m = p^k \cdot c$ , where $\displaystyle c$ is not divisible by $\displaystyle p$ . We have

${} \frac{p^k c}{(k+1)\tau(c)} = p^{p-1} \qquad (**)$ .

We must clearly have $k \ge p-1$ . If $\displaystyle k = p-1$ , then $\frac{c}{\tau(c)}$ must be divisible by $\displaystyle p$ , a contradiction, since $p \nmid c$ . On the other hand, if $\displaystyle k = p$ , then by $\displaystyle (**)$ we have $\displaystyle pc = (p+1)\tau(c)$ . This implies $p \mid \tau(c)$ , so $p \le \tau(c) \le 2\sqrt{c}$ . But by $\displaystyle (*)$ , we have

$\sqrt{c} = \frac{c}{\sqrt{c}} \le \frac{2c}{\tau(c)} = 2p^{p-1} \cdot \frac{p+1}{p^p} = \frac{2(p+1)}{p}$ .

This implies $p \le 2 \sqrt{c} \le \frac{4(p+1)}{p}$ , a contradiction for $p \ge 5$ .

Thus we must have $k \ge p+1$ . Here, we have

$\frac{p^{p-1} (k+1)}{p^k} = \frac{s}{\tau(s)} \ge \frac{s}{2\sqrt{s}} = \frac{\sqrt{s}}{2}$ .

But by induction, we have $\frac{k+1}{p^{k-p+1}} < \frac{1}{2}$ , which implies $\displaystyle s < 1$ , a final contradiction.

Solution 2

As in the first solution, it is sufficient to show that there are infinitely many $\displaystyle a$ such that $\frac{m}{\tau(m)} = a$ has no solutions.

We note that for prime $\displaystyle p$ , $\frac{p^k}{\tau(p^k)} = \frac{p^k}{k+1}$ is a non-decreasing function of $\displaystyle k$ , for $\frac{\frac{p^{k+1}}{k+2}}{\frac{p^k}{k+1}} = \frac{p(k+1)}{k+2} \ge 1$ . We also note that since there are only $\displaystyle m$ positive integers less than or equal to $\displaystyle m$ , ${} \frac{m}{\tau(m)} \ge 1$ . We also note that $\displaystyle \tau$ is a weak multiplicative function, so for relatively prime $\displaystyle m,n$ , $\frac{mn}{\tau(mn)} = \frac{m}{\tau(m)} \cdot \frac{n}{\tau(n)}$ .

Now, suppose that there exists some integer $\displaystyle a_0$ such that for all integers $\displaystyle m$ , $\frac{m}{\tau(m)} \neq a_0$ . Let $\displaystyle p$ be any prime greater than $\displaystyle a_0+1$ . We claim that there is no integer $\displaystyle m$ such that $\frac{m}{\tau(m)} = p^{a_0-1}$ . Suppose the contrary. Clearly, we must have $p^{a_0-1} \mid m$ , so let $m = p^k\cdot c$ , for some $\displaystyle c$ not divisible by $\displaystyle p$ . If $\displaystyle k$ is less than $\displaystyle a_0-1$ , then the numerator of $\frac{m}{\tau(m)}$ is not divisible by $p^{a_0-1}$ , a contradiction. If $\displaystyle k = a_0 -1$ , then we must have $p^{a_0-1} = \frac{p^{a_0-1}}{a_0} \cdot \frac{c}{\tau(c)}$ , which implies $\frac{c}{\tau(c)} = a_0$ , a contradiction. So $\displaystyle k > a_0-1$ . But then we have

$\frac{m}{\tau(m)} \ge \frac{p^{k}}{k+1} \ge \frac{p^{a_0}}{a_0+1} > p^{a_0-1}$ ,

a contradiction. Thus it is sufficient to prove the existance of one $\displaystyle a_0$ such that $\displaystyle \tau(a_0n) = n$ has no solution $\displaystyle n$ .

We will now prove that these is no integer $\displaystyle m$ such that $\frac{m}{\tau(m)} = \frac{6}{5}$ . Suppose that there is such an integer $m$ . Since $5 \mid \tau(m)$ and $\tau \left( \prod_{i=1}^{n}p_i^{e_i} \right) = \prod_{i=1}^n (e_i+1)$ for distinct primes $\displaystyle p_i$ , it follows that $\displaystyle m$ must be divisible by $\displaystyle p^4$ , for some prime $\displaystyle p$ . But then we have

$\frac{m}{\tau(m)} \ge \frac{p^4}{5} \ge \frac{2^4}{5} > \frac{6}{5}$ ,

a contadiction.

We will now prove that for no integer $\displaystyle m$ does the equation $\frac{m}{\tau(m)} = 5^4$ hold. Suppose on the contrary that there exists such an $\displaystyle m$ . We must have $m = 5^{k}\cdot c$ , for some $\displaystyle c$ not divisible by 5. We must clearly have $k \ge 4$ . In fact, we must have $\displaystyle k > 4$ , for $\displaystyle k=4$ gives us ${} \frac{m}{\tau(m)} = \frac{5^4}{4+1} \cdot \frac{c}{\tau(c)} = 5^3 \cdot \frac{c}{\tau(c)}$ , which cannot be divisible by $\displaystyle 5^4$ . We cannot have $\displaystyle k = 5$ , either, since we then have $\frac{m}{\tau(m)} = \frac{5^5}{6} \cdot \frac{c}{\tau(c)}$ , which gives us $\frac{c}{\tau(c)} = \frac{6}{5}$ . Then