Maths Olympiad Prep

Library / /6 of 7

Number theory Difficulty 7.3 National olympiad, round 2 Prove it Vietnam

For a positive integer nn, let τ(n)\tau(n) be the number of positive divisors of nn.

a) Find all positive integers nn such that τ(n)+2023=n\tau(n) + 2023 = n.

b) Prove that there exist infinitely many positive integers kk such that there are exactly two positive integers nn satisfying τ(kn)+2023=n\tau(kn) + 2023 = n.

Solution

a) First, we will prove the following lemma.

Lemma. For any positive integer nn, then τ(n)2n\tau(n) \leq 2\sqrt{n}.

Proof. Consider any positive integer nn, let d1,d2,,dsd_1, d_2, \dots, d_s be all positive divisors not exceeding n\sqrt{n} of nn. Then, obviously we have sns \leq \sqrt{n}.

Note that, if xx is a divisor not less than n\sqrt{n} of nn then nx\frac{n}{x} is a positive divisor not exceeding n\sqrt{n} of nn. It follows that τ(n)2s2n\tau(n) \leq 2s \leq 2\sqrt{n}. \blacksquare

Back to the problem, suppose there exists a positive integer nn satisfying the equation τ(n)+2023=n\tau(n) + 2023 = n. According to the above lemma, we have n2n+2023n \leq 2\sqrt{n} + 2023. Solving this inequality, we get
n(2024+1)2<2115. n \leq (\sqrt{2024} + 1)^2 < 2115.
On the other hand, we also have n=τ(n)+20232025n = \tau(n) + 2023 \ge 2025. Therefore 2025n21142025 \le n \le 2114. Let n=p1e1p2e2pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} where p1,p2,,pkp_1, p_2, \dots, p_k are distinct primes and e1,e2,,eke_1, e_2, \dots, e_k are positive integers. Then τ(n)=(e1+1)(e2+1)(ek+1)\tau(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1) and the equation τ(n)+2023=n\tau(n) + 2023 = n can be rewritten as
(e1+1)(e2+1)(ek+1)+2023=p1e1p2e2pkek(1) (e_1 + 1)(e_2 + 1)\cdots (e_k + 1) + 2023 = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \quad (1)
If e1,e2,,eke_1, e_2, \dots, e_k are all even numbers, then nn is a perfect square, and 2025n21142025 \le n \le 2114 so n=2025n = 2025. However, when try again, this value does not satisfy the equation. Therefore, among the numbers e1,e2,,eke_1, e_2, \dots, e_k there must be at least one odd number. From here, combined with equation (1), we deduce that p1,p2,,pkp_1, p_2, \dots, p_k are odd prime numbers. Without loss of generality, assume 3p1<p2<<pk3 \le p_1 < p_2 < \dots < p_k.

If k5k \ge 5, then we have n=p1e1p2e2pkek3571113>2114n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \ge 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 > 2114, a contradiction. Therefore k4k \le 4.

Case 1: k=1k = 1. In this case, we have 2114n=p1e13e12114 \ge n = p_1^{e_1} \ge 3^{e_1}. Therefore e16e_1 \le 6. Checking each case of the value of e1e_1, we find no prime number p1p_1 that satisfies the equation (1).

Case 2: k=2k = 2. In this case, we have 2114n=p1e1p2e23e15e23e1+e2152114 \ge n = p_1^{e_1} p_2^{e_2} \ge 3^{e_1} 5^{e_2} \ge 3^{e_1+e_2-1} \cdot 5, deduce e1+e26e_1 + e_2 \le 6. From there
τ(n)=(e1+1)(e2+1)(e1+e2+22)29. \tau(n) = (e_1 + 1)(e_2 + 1) \le \left( \frac{e_1 + e_2 + 2}{2} \right)^2 \le 9.
Checking specific cases of τ(n)\tau(n), we find no corresponding value of nn satisfying the equation.

Case 3: k=3k = 3. In this case, we have
2114n=p1e1p2e2p3e33e15e27e33e1+e2+e3257, 2114 \ge n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \ge 3^{e_1} 5^{e_2} 7^{e_3} \ge 3^{e_1+e_2+e_3-2} \cdot 5 \cdot 7,
infers e1+e2+e35e_1 + e_2 + e_3 \le 5. Which e1+e2+e33e_1 + e_2 + e_3 \ge 3 so e1+e2+e3{3,4,5}e_1 + e_2 + e_3 \in \{3, 4, 5\}, infers (e1,e2,e3)(e_1, e_2, e_3) is a permutation of one of the sets of numbers (1,1,1)(1, 1, 1), (1,1,2)(1, 1, 2), (1,1,3)(1, 1, 3), (1,2,2)(1, 2, 2). From there τ(n){8,12,16,18}\tau(n) \in \{8, 12, 16, 18\}. Checking all the specific cases of τ(n)\tau(n), we find no corresponding value of nn which satisfies the equation.

Case 4: k=4k = 4. In this case, we have 2114n=p1e1p2e2p3e3p4e43e15e27e311e42114 \ge n = p_1^{e_1} p_2^{e_2} p_3^{e_3} p_4^{e_4} \ge 3^{e_1} 5^{e_2} 7^{e_3} 11^{e_4}. If e1,e2,e3,e4e_1, e_2, e_3, e_4 has a large number than 1, then 3e15e27e311e4325711>21143^{e_1} 5^{e_2} 7^{e_3} 11^{e_4} \ge 3^2 \cdot 5 \cdot 7 \cdot 11 > 2114, which is a contradiction. Therefore e1=e2=e3=e4=1e_1 = e_2 = e_3 = e_4 = 1, i.e. τ(n)=(e1+1)(e2+1)(e3+1)(e4+1)=16\tau(n) = (e_1+1)(e_2+1)(e_3+1)(e_4+1) = 16. However, when substituting back to the equation τ(n)+2023=n\tau(n)+2023 = n, we find no corresponding value nn which satisfies.

So, the equation τ(n)+2023=n\tau(n)+2023 = n has no positive integer solution.

b) All prime numbers k>6996k > 6996 satisfy the problem requirements. Indeed, considering any prime number kk, greater than 6996. We have the following comment
τ(kn)2τ(n). \tau(kn) \le 2\tau(n).
Indeed, let n=kep1e1p2e2psesn = k^e \cdot p_1^{e_1} p_2^{e_2} \cdots p_s^{e_s}, where p1,p2,,psp_1, p_2, \dots, p_s is Other distinct prime numbers kk; e1,e2,,ese_1, e_2, \dots, e_s are positive integers and ee is a natural number. Then, we have
τ(kn)=(e+2)(e1+1)(e2+1)(es+1)2(e+1)(e1+1)(e2+1)(es+1)=2τ(n). \tau(kn) = (e+2)(e_1+1)(e_2+1)\cdots(e_s+1) \le 2(e+1)(e_1+1)(e_2+1)\cdots (e_s+1) = 2\tau(n).
In addition, we also see that, if nn is not divisible by kk (i.e. e=0e = 0), then τ(kn)=2τ(n)\tau(kn) = 2\tau(n).

Now, consider a positive integer solution nn (if any) of the equation τ(kn)+2023=n\tau(kn) + 2023 = n. Using the above result, combined with the Lemma in part a), we have
n=τ(kn)+20232τ(n)+20234n+2023. n = \tau(kn) + 2023 \le 2\tau(n) + 2023 \le 4\sqrt{n} + 2023.
Solving the inequality n4n+2023n \le 4\sqrt{n}+2023, we get n(2+2027)2<6996<kn \le (2 + \sqrt{2027})^2 < 6996 < k. It follows that nn is not divisible by kk, from which τ(kn)=2τ(n)\tau(kn) = 2\tau(n) and the equation τ(kn)+2023=n\tau(kn)+2023 = n is rewritten as
2τ(n)+2023=n.(2) 2\tau(n) + 2023 = n. \qquad (2)
We will prove that equation (2) has exactly two solutions: n=2027n = 2027 and n=2031n = 2031. Indeed, above, we have proved
n(2+2027)2<2212. n \le (2 + \sqrt{2027})^2 < 2212.
Furthermore, from (2), we have n=2τ(n)+20232027n = 2\tau(n)+2023 \ge 2027. Therefore 2027n22112027 \le n \le 2211. Let n=p1e1p2e2psesn = p_1^{e_1} p_2^{e_2} \cdots p_s^{e_s} where p1,p2,,psp_1, p_2, \dots, p_s are distinct primes and e1,e2,,ese_1, e_2, \dots, e_s are positive integers. Then τ(n)=(e1+1)(e2+1)(es+1)\tau(n) = (e_1+1)(e_2+1)\cdots(e_s+1) and equation (2) can be rewritten as
2(e1+1)(e2+1)(es+1)+2023=p1e1p2e2pses.(3) 2(e_1 + 1)(e_2 + 1)\cdots (e_s + 1) + 2023 = p_1^{e_1} p_2^{e_2} \cdots p_s^{e_s}. \quad (3)
From equation (3), we deduce that p1,p2,,psp_1, p_2, \dots, p_s are odd prime numbers. Without loss of generality, assume that 3p1<p2<<ps3 \le p_1 < p_2 < \dots < p_s. At this point, we note that, if s5s \ge 5 then
2211n=p1e1p2e2pses3571113>2211, 2211 \ge n = p_1^{e_1} p_2^{e_2} \cdots p_s^{e_s} \ge 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 > 2211,
which is a contradiction. Therefore s4s \le 4. Consider the following cases.

Case 1: s=1s = 1. In this case, we have 2211n=p1e13e12211 \ge n = p_1^{e_1} \ge 3^{e_1}. Therefore e17e_1 \le 7. Checking all values of e1e_1, we find exactly one solution n=2027n = 2027 which satisfies.

Case 2: s=2s = 2. In this case, we have
2211n=p1e1p2e23e15e23e1+e215, 2211 \ge n = p_1^{e_1} p_2^{e_2} \ge 3^{e_1} 5^{e_2} \ge 3^{e_1+e_2-1} \cdot 5,
so e1+e26e_1 + e_2 \le 6. It follows that
τ(n)=(e1+1)(e2+1)(e1+e2+22)29. \tau(n) = (e_1 + 1)(e_2 + 1) \le \left( \frac{e_1 + e_2 + 2}{2} \right)^2 \le 9.
Checking all cases of τ(n)\tau(n), we find exactly one value n=2031n = 2031 which satisfies.

Case 3: s=3s = 3. In this case, we have
2211n=p1e1p2e2p3e33e15e27e33e1+e2+e3257, 2211 \ge n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \ge 3^{e_1} 5^{e_2} 7^{e_3} \ge 3^{e_1+e_2+e_3-2} \cdot 5 \cdot 7,
therefore e1+e2+e35e_1 + e_2 + e_3 \le 5. So e1+e2+e3{3,4,5}e_1 + e_2 + e_3 \in \{3, 4, 5\}, therefore (e1,e2,e3)(e_1, e_2, e_3) is a permutation of one of the following triplets (1,1,1),(1,1,2),(1,1,3),(1,2,2)(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2). We deduce that τ(n){8,12,16,18}\tau(n) \in \{8, 12, 16, 18\}. Checking all cases of τ(n)\tau(n), we find no corresponding value nn which satisfies.

Case 4: s=4s = 4. In this case, we have
2211n=p1e1p2e2p3e3p4e43e15e27e311e4. 2211 \ge n = p_1^{e_1} p_2^{e_2} p_3^{e_3} p_4^{e_4} \ge 3^{e_1} 5^{e_2} 7^{e_3} 11^{e_4}.
If one of e1,e2,e3,e4e_1, e_2, e_3, e_4 is greater than 1, then 3e15e27e311e4325711>22113^{e_1} 5^{e_2} 7^{e_3} 11^{e_4} \ge 3^2 \cdot 5 \cdot 7 \cdot 11 > 2211, which is a contradiction. Therefore e1=e2=e3=e4=1e_1 = e_2 = e_3 = e_4 = 1, i.e. τ(n)=(e1+1)(e2+1)(e3+1)(e4+1)=16\tau(n) = (e_1 + 1)(e_2 + 1)(e_3 + 1)(e_4 + 1) = 16. However, when substituting back to equation (2), we find no corresponding value of nn which satisfies.

Thus, the equation (2) has exactly two positive integer solutions: n=2027n = 2027 and n=2031n = 2031. It follows that the equation τ(kn)+2023=n\tau(kn) + 2023 = n has exactly two positive integer solutions: n=2027n = 2027 and n=2031n = 2031. Hence the problem is proved. \square

Want a route through all this instead of 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.