2015 Brazilian Math Olympiad Number theory problem

For $n\in\mathbb{Z}_{>1}$ write $n=p_1^{a_1}\cdot\ldots\cdot p_r^{a_r}$ with pairwise distinct prime numbers $p_i$. Now define the "fake derivative" of $n$ by $$f(n)=a_1\cdot p_1^{a_1-1}\cdot\ldots\cdot a_r\cdot p_r^{a_r-1}$$ Show that there are infinitely many numbers $n$ satisfying $$f(n)=f(n-1)+1$$

I've been facing this question for the last two weeks. Despite I didn't solve it, I noticed some properties of this "fake derivative" function. In the following, $\sigma$ will denote a permutation of $r$ letters, where $r$ stands for the number of distinct prime factors of $n$ and $p_i\neq p_j$ whenever $i\neq j$.

• $f(p_1\cdot\ldots\cdot p_r)=1$
• $f(n)=n$ if, and only if, $a_1\cdot\ldots\cdot a_r=p_1\cdot\ldots\cdot p_r$
• In particular, if $n=p_1^{p_{\sigma(1)}}\cdot\ldots\cdot p_r^{p_{\sigma(r)}}$ then $f(n)=n$
• No prime number is in the image of $f$
• $f(n^k)=k^r\cdot n^{k-1}\cdot f(n)$ for all integers $k\geq 1$
• $f(p_1^{a_1}\cdot\ldots\cdot p_r^{a_r})=f(p_1^{a_1})\cdot\ldots\cdot f(p_r^{a_r})$
• In particular, if $\text{gcd}(m,n)=1$ then $f(n\cdot m)=f(n)\cdot f(m)$

I solved a kind of weaker version of the problem: there are infinitely many pairs $(n,m)$ such that $f(n)=f(m)+1$. Indeed, to prove this we only need to find one such pair, say, $(n_0,m_0)$ and then take $(n,m)=(p\cdot n_0, p\cdot m_0)$, where $p$ is any prime number that doesn't divide $n_0$ or $m_0$. Once there are finitely many primes that divide $n_0$ or $m_0$, there are infinitely many primes satisfying the preceding condition, and we are done. We can take, for example $(n_0,m_0)=(3^3,13^2)$. I found four other pairs: $(5^3,37^2)$, $(11^3,181^2)$, $(7^231^2,17^3)$ and $(19^3,541^2)$.

I also noticed that if $f(n)=n$ and $f(n-1)=n-1$, then the result obviously holds. But by the second property, we would have $n=p_1^{p_{\sigma(1)}}\ldots p_r^{p_{\sigma(r)}}$ and $n-1=q_1^{q_{\sigma(1)}}\ldots q_s^{q_{\sigma(s)}}$, where the $p_i$'s and $q_j$'s are pairwise distinct, since the primes that divide $n$ doesn't divide $n-1$. So if we find infinitely many numbers $n$ such that $n$ and $n-1$ are products of primes raised to a permutation of themselves, we are done.

Another thing that can (or cannot) be useful: the equation $f(n)=f(n-1)+1$ is equivalent to $f(n^2-n)=f(n)^2-f(n)$ (just use the fact that $\text{gcd}(n,n-1)=1$ and the last property).

You can read this problem (in Portuguese) here. It's problem 3.

Solution 1:

Not a complete proof but i think this might work..

Starting from your weaker version:
We can find pairs $(n,m)$ such that $f(n)=f(m)+1$ and $\gcd(n,m)=1$. You have already given a couple of those above.
With one such pair we can find infinitely many other pairs $(n_i,m_i)=(p_i\cdot n, q_i\cdot m)$ where $p_i$ is any prime number satisfying: $p_i \nmid n$ and $q_i$ is any prime number satisfying: $q_i \nmid m$ , also $p_i\neq q_i$.
We see that: $f(n_i)=f(m_i)+1$ and $\gcd(n_i,m_i)=1$ .
Now Bezout's identity and the fact that $ \gcd(n_i,m_i)=1 $ tell us that we can find infinitely many pairs $ (x_j,y_j) $ such that $y_j\cdot m_i=x_j\cdot n_i -1 $ with: $ (x_j,y_j) = (x_0+k\cdot m_i,y_0+k\cdot n_i)$ for any integer $ k $.
It seems to me that we must always be able to find $ k $ for which $ (x_j,y_j) $ consists of only primes to the first power that are not in $(n_i,m_i)$.