For each positive integer $n$, let $\tau (n)$ be the number of positive divisors of $n$. a) Find all positive integers $n$ such that $\tau(n)+2023=n$. b) Prove that there exist infinitely many positive integers $k$ such that there are exactly two positive integers $n$ satisfying $\tau(kn)+2023=n$.
Problem
Source: 2024 Vietnam National Olympiad - Problem 6
Tags: number theory
P2nisic
06.01.2024 13:25
a) i get no such $n$ b) First we provethat the equation $2\tau(n)+2023=n$ haw only two sollution $n=2027,2031$ then we take $k=q$ with $q=prime>M$ for some integer $M$ large enough If $q$ doeσ not devise $n$ then we have $2\tau(n)+2023=n$ If $q|n$ we prove that: $n$ is large enough to satisfy the equation $2\tau(n)+2023=n$ So there are infinitive $k=q$ with $q=prime>M$ such that the equation:$\tau(kn)+2023=n$ haw exactly two sollution.
Aliosman
06.01.2024 14:23
$2027$ doesn't satisfy the equation $4\tau(n)+2023=n$
Aliosman
06.01.2024 14:26
b) let $k=q$ prime with large enough. $2\tau(n)+2023=n$ has two solutions $n=2027,2031$
wassupevery1
07.01.2024 19:54
We first use the lemma $\tau(n)<2\sqrt{n}$ to get $n=\tau(n)+2023<2\sqrt{n}+2023$.
This gives $n<46^2=2116$.
The problem condition implies $n > 2023$, hence $n \geq 2+2023=2025$.
In addition, $n= 2025$ fails so $2026 \leq n \leq 2115$. But this means $n$ is not a perfect square, so $\tau(n)$ is even, implying that $n$ is odd.
Considering all odd $n$'s varying from $2026$ to $2115$, we can use the $\tau(n)$ formula to get that $\tau(n) \leq 16$.
This gives $n \geq 2023+16 = 2039$.
Now, directly checking all odd $n$'s from $2027$ to $2039$ gives no such $n$.
Hence, there are no positive integers $n$ such that $\tau(n)+2023=n$.
We claim all primes $k>2040$ work.
First, if $k \mid n$, write $n = k^a \cdot l$ for some positive integers $a, l$ with $(l, k)=1$.
Then the equation is equivalent to $(a+1) \tau(l) + 2023 = k^a \cdot l$.
We use the lemma $\tau(l)<2\sqrt{l}$ to get $k^a \cdot l < 2(a+1) \sqrt{l} + 2023$.
Now, consider the function $f(x)=k^ax^2-2(a+1)x-2023$ for $x \geq 1$. We get that $f'(x)=2(k^ax-(a+1)) \geq 2(k^a-(a+1))>0,$ so the function is increasing on $[1, \infty)$. This means $f(\sqrt{l}) \geq f(1)=k^a-(2a+2025)>0,$ absurd.
This means $(n, k)=1$. The equation is now $2\tau(n)+2023=n$.
The condition implies $n > 2023$, hence $n \geq 2+2023=2025$.
We now use the lemma $\tau(n)<2\sqrt{n}$ to get $n<4\sqrt{n}+2023$, so $n \leq 2218$.
In addition, $n= 2025$ fails and $n$ is odd, so $2027 \leq n \leq 2218$.
Considering all odd $n$'s varying from $2026$ to $2218$, we can use the $\tau(n)$ formula to get that $\tau(n) \leq 16$.
This gives $n \geq 2023+16 = 2039$.
Now, directly checking all odd $n$'s from $2027$ to $2039$ gives $n=2027$ and $n=2031$.
Our claim is proved, the problem is solved.