For all $n>1$, let $f(n)$ be the biggest divisor of $n$ except itself. Does there exists a positive integer $k$ such that the equality $n-f(n)=k$ has exactly $2023$ solutions?
Problem
Source: 2023 Turkey TST D1 P3
Tags: number theory, equation
29.03.2023 20:18
By induction over $\ell$, let’s prove that there exist an integer $k$ such that $k+1$ is prime and the number of solutions of $n-f(n)=k$ is exactly $\ell$. For the base case $\ell=3$, choose $k=6$. Assume that we have an integer $m$ such that $n-f(n)=m$ has $x$ solutions and $m+1$ is a prime number. As $f(n)=\frac n{\text{smallest prime divisor of }n}$, we know that the number of solutions of $n-f(n)=y$ equals to the number of prime numbers $q$ such that for any prime number $f<q$, we have $V_f(q-1)=V_f(y)$ (call the prime number $q$ proper divisor of $y$ if $q$ satisfies this condition). Let the proper divisors of $m$ be $p_1<p_2<\cdots <p_x$ (we know that there are $x$ such primes). Also, clearly, $m+1$ is the largest such prime number. Hence, $p_x=m+1$. See that there are infinitely many prime numbers $s$ such that $V_e(s-1)=V_e(m)$ for all prime numbers $e$ less than $p_x$. Choose the smallest such prime number that’s greater than $p_x=m+1$, say $Q$. As all prime divisors of $m$ are less than $p_x$, we get $m|Q-1$. Hence, we get that $p_1, p_2, \cdots ,p_x$ are all proper divisors of $Q-1$. In addition, $Q>p_x$ is a proper divisor of $Q-1$. Now, assume that $Q-1$ has a proper divisor different than $p_1<p_2<\cdots<p_x<Q$. Let this prime number be $r$. Evidently, $Q>r$. If $p_x>r$, then for any prime number $w<r$, we get $V_w(r-1)=V_w(Q-1)=V_w(p_x-1)$. Then, $r$ is a proper divisor of $m=p_x-1$, which leads to a contradiction. If $r>p_x$, then for any prime number $w<p_x<r$, we get $V_w(r-1)=V_w(Q-1)=V_w(p_x-1)=V_w(m)$. However, $Q$ was the smallest prime divisors greater than $p_x$ that satisfies this condition. As $Q>r>p_x$, we get a contradiction. Overall, we proved that all the proper divisors of $Q-1$ are $p_1<p_2<\cdots<p_x<Q$, hence a total of $x+1$ proper divisors. Therefore, the equation $n-f(n)=Q-1$ has exactly $x+1$ solutions where $Q$ is a prime number. This completes the induction.