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

$\frac{m}{\tau(m)} \ge \frac{5^k}{k+1} \ge \frac{5^6}{7} > 5^4$,

a contradiction. Thus $\displaystyle m$ does not exist and the problem is solved.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources