Number theoryDifficulty 7.3National olympiad, round 2Prove itVietnam
For a positive integer n, let τ(n) be the number of positive divisors of n.
a) Find all positive integers n such that τ(n)+2023=n.
b) Prove that there exist infinitely many positive integers k such that there are exactly two positive integers n satisfying τ(kn)+2023=n.
Solution
a) First, we will prove the following lemma.
Lemma. For any positive integer n, then τ(n)≤2n.
Proof. Consider any positive integer n, let d1,d2,…,ds be all positive divisors not exceeding n of n. Then, obviously we have s≤n.
Note that, if x is a divisor not less than n of n then xn is a positive divisor not exceeding n of n. It follows that τ(n)≤2s≤2n. ■
Back to the problem, suppose there exists a positive integer n satisfying the equation τ(n)+2023=n. According to the above lemma, we have n≤2n+2023. Solving this inequality, we get n≤(2024+1)2<2115. On the other hand, we also have n=τ(n)+2023≥2025. Therefore 2025≤n≤2114. Let n=p1e1p2e2⋯pkek where p1,p2,…,pk are distinct primes and e1,e2,…,ek are positive integers. Then τ(n)=(e1+1)(e2+1)⋯(ek+1) and the equation τ(n)+2023=n can be rewritten as (e1+1)(e2+1)⋯(ek+1)+2023=p1e1p2e2⋯pkek(1) If e1,e2,…,ek are all even numbers, then n is a perfect square, and 2025≤n≤2114 so n=2025. However, when try again, this value does not satisfy the equation. Therefore, among the numbers e1,e2,…,ek there must be at least one odd number. From here, combined with equation (1), we deduce that p1,p2,…,pk are odd prime numbers. Without loss of generality, assume 3≤p1<p2<⋯<pk.
If k≥5, then we have n=p1e1p2e2⋯pkek≥3⋅5⋅7⋅11⋅13>2114, a contradiction. Therefore k≤4.
Case 1:k=1. In this case, we have 2114≥n=p1e1≥3e1. Therefore e1≤6. Checking each case of the value of e1, we find no prime number p1 that satisfies the equation (1).
Case 2:k=2. In this case, we have 2114≥n=p1e1p2e2≥3e15e2≥3e1+e2−1⋅5, deduce e1+e2≤6. From there τ(n)=(e1+1)(e2+1)≤(2e1+e2+2)2≤9. Checking specific cases of τ(n), we find no corresponding value of n satisfying the equation.
Case 3:k=3. In this case, we have 2114≥n=p1e1p2e2p3e3≥3e15e27e3≥3e1+e2+e3−2⋅5⋅7, infers e1+e2+e3≤5. Which e1+e2+e3≥3 so e1+e2+e3∈{3,4,5}, infers (e1,e2,e3) is a permutation of one of the sets of numbers (1,1,1), (1,1,2), (1,1,3), (1,2,2). From there τ(n)∈{8,12,16,18}. Checking all the specific cases of τ(n), we find no corresponding value of n which satisfies the equation.
Case 4:k=4. In this case, we have 2114≥n=p1e1p2e2p3e3p4e4≥3e15e27e311e4. If e1,e2,e3,e4 has a large number than 1, then 3e15e27e311e4≥32⋅5⋅7⋅11>2114, which is a contradiction. Therefore e1=e2=e3=e4=1, i.e. τ(n)=(e1+1)(e2+1)(e3+1)(e4+1)=16. However, when substituting back to the equation τ(n)+2023=n, we find no corresponding value n which satisfies.
So, the equation τ(n)+2023=n has no positive integer solution.
b) All prime numbers k>6996 satisfy the problem requirements. Indeed, considering any prime number k, greater than 6996. We have the following comment τ(kn)≤2τ(n). Indeed, let n=ke⋅p1e1p2e2⋯pses, where p1,p2,…,ps is Other distinct prime numbers k; e1,e2,…,es are positive integers and e 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). In addition, we also see that, if n is not divisible by k (i.e. e=0), then τ(kn)=2τ(n).
Now, consider a positive integer solution n (if any) of the equation τ(kn)+2023=n. Using the above result, combined with the Lemma in part a), we have n=τ(kn)+2023≤2τ(n)+2023≤4n+2023. Solving the inequality n≤4n+2023, we get n≤(2+2027)2<6996<k. It follows that n is not divisible by k, from which τ(kn)=2τ(n) and the equation τ(kn)+2023=n is rewritten as 2τ(n)+2023=n.(2) We will prove that equation (2) has exactly two solutions: n=2027 and n=2031. Indeed, above, we have proved n≤(2+2027)2<2212. Furthermore, from (2), we have n=2τ(n)+2023≥2027. Therefore 2027≤n≤2211. Let n=p1e1p2e2⋯pses where p1,p2,…,ps are distinct primes and e1,e2,…,es are positive integers. Then τ(n)=(e1+1)(e2+1)⋯(es+1) and equation (2) can be rewritten as 2(e1+1)(e2+1)⋯(es+1)+2023=p1e1p2e2⋯pses.(3) From equation (3), we deduce that p1,p2,…,ps are odd prime numbers. Without loss of generality, assume that 3≤p1<p2<⋯<ps. At this point, we note that, if s≥5 then 2211≥n=p1e1p2e2⋯pses≥3⋅5⋅7⋅11⋅13>2211, which is a contradiction. Therefore s≤4. Consider the following cases.
Case 1:s=1. In this case, we have 2211≥n=p1e1≥3e1. Therefore e1≤7. Checking all values of e1, we find exactly one solution n=2027 which satisfies.
Case 2:s=2. In this case, we have 2211≥n=p1e1p2e2≥3e15e2≥3e1+e2−1⋅5, so e1+e2≤6. It follows that τ(n)=(e1+1)(e2+1)≤(2e1+e2+2)2≤9. Checking all cases of τ(n), we find exactly one value n=2031 which satisfies.
Case 3:s=3. In this case, we have 2211≥n=p1e1p2e2p3e3≥3e15e27e3≥3e1+e2+e3−2⋅5⋅7, therefore e1+e2+e3≤5. So e1+e2+e3∈{3,4,5}, therefore (e1,e2,e3) is a permutation of one of the following triplets (1,1,1),(1,1,2),(1,1,3),(1,2,2). We deduce that τ(n)∈{8,12,16,18}. Checking all cases of τ(n), we find no corresponding value n which satisfies.
Case 4:s=4. In this case, we have 2211≥n=p1e1p2e2p3e3p4e4≥3e15e27e311e4. If one of e1,e2,e3,e4 is greater than 1, then 3e15e27e311e4≥32⋅5⋅7⋅11>2211, which is a contradiction. Therefore e1=e2=e3=e4=1, i.e. τ(n)=(e1+1)(e2+1)(e3+1)(e4+1)=16. However, when substituting back to equation (2), we find no corresponding value of n which satisfies.
Thus, the equation (2) has exactly two positive integer solutions: n=2027 and n=2031. It follows that the equation τ(kn)+2023=n has exactly two positive integer solutions: n=2027 and n=2031. Hence the problem is proved. □
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.