IMO 2004 SL N1

Origin: BLR | Category: Number Theory

Problem

Let \tau(n) denote the number of positive divisors of the positive integer n. Prove that there exist infinitely many positive integers a such that the equation \tau(an) = n does not have a positive integer solution n.

Solution

Setting m = an we reduce the given equation to m/\tau(m) = a. Let us show that for a = pp−1 the above equation has no solutions in N if p > 3 is a prime. Assume to the contrary that m \inN is such that m = pp−1\tau(m). Then pp−1 | m, so we may set m = p\alphak, where \alpha, k \inN, \alpha \geqp −1, and p ∤k. Let k = p\alpha1 1 \cdot \cdot \cdot p\alphar r be the decomposition of k into primes. Then \tau(k) = (\alpha1 + 1) \cdot \cdot \cdot (\alphar + 1) and \tau(m) = (\alpha + 1)\tau(k). Our equation becomes p\alpha−p+1k = (\alpha + 1)\tau(k). (1) We observe that \alpha ̸= p−1: otherwise the RHS would be divisible by p and the LHS would not be so. It follows that \alpha \geqp, which also easily implies that p\alpha−p+1 \geq p p+1(\alpha + 1). Furthermore, since \alpha + 1 cannot be divisible by p\alpha−p+1 for any \alpha \geqp, it follows that p | \tau(k). Thus if p | \tau(k), then at least one \alphai+1 is divisible by p and consequently \alphai \geqp−1 for some i. Hence k \geq p \alphai i \alphai+1\tau(k) \geq2p−1 p \tau(k). But then we have p\alpha−p+1k \geq p p + 1(\alpha + 1) \cdot 2p−1 p \tau(k) > (\alpha + 1)\tau(k), contradicting (1). Therefore (1) has no solutions in N. Remark. There are many other values of a for which the considered equa- tion has no solutions in N: for example, a = 6p for a prime p \geq5.