Olympiad Maths Prep

Library / /5 of 6

Number theory Difficulty 7.3 National olympiad, round 2 Prove it Czech-Polish-Slovak Mathematical Match

For any positive integer nn, let τ(n)\tau(n) denote the number of positive divisors of nn and φ(n)\varphi(n) the number of positive integers not greater than nn which are relatively prime to nn. Find all positive integers nn for which one of the three numbers nn, τ(n)\tau(n), and φ(n)\varphi(n) is the arithmetic mean of the other two.

Solution

We have τ(1)=φ(1)=1\tau(1) = \varphi(1) = 1, that is n=1n = 1 satisfies the given condition. In the following, we assume n>1n > 1. For such nn, clearly τ(n)n\tau(n) \le n and φ(n)<n\varphi(n) < n. This means nn cannot be the arithmetic mean of τ(n)\tau(n) and φ(n)\varphi(n). We are left with two cases.

*Case 1:* τ(n)=12(φ(n)+n)\tau(n) = \frac{1}{2}(\varphi(n) + n). Then we have τ(n)>12n\tau(n) > \frac{1}{2}n. For each divisor dd of nn, the number n/dn/d is also the divisor. One of the numbers d,n/dd, n/d is less or equal n\sqrt{n}, which means the set {1,2,,n}\{1, 2, \dots, \lfloor\sqrt{n}\rfloor\} contains at least half of the divisors¹. This clearly implies 12τ(n)n\frac{1}{2}\tau(n) \le \sqrt{n}. We get
2nτ(n)>12n4n>14n216>n. 2\sqrt{n} \ge \tau(n) > \frac{1}{2}n \quad \Rightarrow \quad 4n > \frac{1}{4}n^2 \quad \Rightarrow \quad 16 > n.
For 1<n<161 < n < 16, we can easily calculate τ(n)\tau(n), check the condition τ(n)>12n\tau(n) > \frac{1}{2}n, and calculate φ(n)\varphi(n) in the remaining few cases:

| n | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|-----|---|---|---|---|---|---|---|---|----|----|----|----|----|----|
| τ(n)\tau(n) | 2 | 2 | 3 | 2 | 4 | 2 | 4 | 3 | 4 | 2 | 6 | 2 | 4 | 4 |
| τ(n)>1/2n\tau(n) > 1/2 n ? | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| φ(n)\varphi(n) | 1 | 2 | 2 | | 2 | | | | | | | | | |
| τ(n)=1/2(φ(n)+n)\tau(n) = 1/2 (\varphi(n) + n) ? | × | × | ✓ | | ✓ | | | | | | | | | |

We have n=4n = 4 and n=6n = 6 as solutions.

*Case 2:* φ(n)=12(τ(n)+n)\varphi(n) = \frac{1}{2}(\tau(n) + n). We transform this relation into
τ(n)=2φ(n)n.(1) \tau(n) = 2\varphi(n) - n. \qquad (1)
If nn is even, then no even number is relatively prime to nn, thus φ(n)12n\varphi(n) \le \frac{1}{2}n. But then from (1) we get τ(n)0\tau(n) \le 0, which is impossible. Therefore, nn must be odd. Then (1) implies τ(n)\tau(n) must be odd as well, which means nn is a perfect square (of an odd number). Write the prime factorization of nn in the form
n=p12α1pk2αk,k1, pi3, αi1. n = p_1^{2\alpha_1} \cdots p_k^{2\alpha_k}, \quad k \ge 1, \ p_i \ge 3, \ \alpha_i \ge 1.

Applying the well-known formula for τ(n)\tau(n) and φ(n)\varphi(n), we rewrite (1) as
(2α1+1)(2αk+1)=2p12α11(p11)pk2αk1(pk1)p12α1pk2αk==p12α11pk2αk1(2(p11)(pk1)p1pk). (2\alpha_1 + 1) \cdots (2\alpha_k + 1) = 2p_1^{2\alpha_1-1}(p_1-1) \cdots p_k^{2\alpha_k-1}(p_k-1) - p_1^{2\alpha_1} \cdots p_k^{2\alpha_k} = \\ = p_1^{2\alpha_1-1} \cdots p_k^{2\alpha_k-1}(2(p_1-1) \cdots (p_k-1) - p_1 \cdots p_k).
The right hand side is divisible by p12α11pk2αk1p_1^{2\alpha_1-1} \cdots p_k^{2\alpha_k-1}, and so must be the left hand side as well. From this, we obtain
p12α11pk2αk1(2α1+1)(2αk+1).(2) p_1^{2\alpha_1-1} \cdots p_k^{2\alpha_k-1} \le (2\alpha_1 + 1) \cdots (2\alpha_k + 1). \quad (2)
However, for every integers p3p \ge 3 and α1\alpha \ge 1, the inequality p2α1(2α+1)p^{2\alpha-1} \ge (2\alpha + 1) holds, with equality only for p=3p = 3 and α=1\alpha = 1. To prove this, we use induction on α\alpha: The case α=1\alpha = 1 is trivial (with equality only for p=3p = 3) and when α\alpha increases by 1, the right hand size increases by 2, while the left hand size increases by 1.
p2(α+1)1p2α1=p2α1(p21)>2. p^{2(\alpha+1)-1} - p^{2\alpha-1} = p^{2\alpha-1}(p^2 - 1) > 2.
Therefore, each of the (positive) factors on the left hand side of (2) is greater or equal than the corresponding factor on the right hand side. The only possible way to satisfy (2) is to put k=1k = 1, p1=3p_1 = 3, α1=1\alpha_1 = 1, that is, n=9n = 9. Indeed, we have τ(9)=3\tau(9) = 3 and φ(9)=6\varphi(9) = 6, thus (1) holds for n=9n = 9.

Answer. The given condition is fulfilled for n{1,4,6,9}n \in \{1, 4, 6, 9\}.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.