Number of solutions to this nice equation $\varphi(n)+\tau(n^2)=n$

Question

How many natural numbers $n$ satisfy the equation$$\varphi(n)+\tau(n^2)=n$$where $\varphi$ is the Euler's totient function and $\tau$ is the divisor function i.e. number of divisors of an integer.

I made this equation and I think it is not hard. I haven't solved this completely yet, so I want you to work on this along with me. I'd love to see your solutions!

Answer 1

Hint: You can show that $n$ is odd and has at most two (distinct) prime factors. Then, it follows that $n=21$ and $n=25$ are the only solutions.

Further Hint: Suppose $n=p^aq^br^cm$ where $p,q,r,a,b,c\in\mathbb{N}$ with $p,q,r$ being pairwise distinct primes, and $m\in\mathbb{N}$ is not divisible by $p$, $q$, or $r$. Prove that $$n-\phi(n)> n\left(\frac{1}{2p}+\frac{1}{q}+\frac{1}{r}\right)>\tau\left(n^2\right)\,,$$ provided that $p,q,r$ are the smallest primes dividing $n$ with $2<p<q<r$.

Remark: I posted weaker inequalities (now removed for being redundant), and realized that I could make a significant improvement from what I had gotten in my scratch work. A complete solution is in the hidden portion below.

Let $u_1,u_2,\ldots,u_k$ be distinct prime numbers dividing $m$. Then, $$\begin{align}n-\phi(n)&=n\left(1-\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\,\prod_{i=1}^k\,\left(1-\frac{1}{u_i}\right)\right)\\&\geq n\Biggl(1-\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\Biggr)\\&>n\Biggl(\left(\frac{1}{p}-\frac{1}{pq}-\frac{1}{pr}-\frac{1}{qr}\right)+\frac{1}{q}+\frac{1}{r}\Biggr)\\&>n\Biggl(\left(\frac{1}{p}-\frac{1}{5p}-\frac{1}{7p}-\frac{1}{7p}\right)+\frac{1}{q}+\frac{1}{r}\Biggr)>n\left(\frac{1}{2p}+\frac{1}{q}+\frac{1}{r}\right)\,.\end{align}$$ First, note that $m\geq\tau\left(m^2\right)$. If $b>1$, then $$\frac{n}{q}= p^aq^{b-1}r^cm> (2a+1)(2b+1)(2c+1)\,\tau\left(m^2\right)\geq \tau\left(n^2\right)\,.$$ Similarly, if $c>1$, then $$\frac{n}{r}> \tau\left(n^2\right)\,.$$ If $a>1$ and $b=c=1$, then $$\frac{n}{2p}=\frac{1}{2}p^{a-1}qrm> 9(2a+1)\,\tau\left(m^2\right)=\tau\left(n^2\right)\,.$$ If $a=b=c=1$, then $$n\left(\frac{1}{q}+\frac{1}{r}\right)=p(q+r)m> 27\,\tau\left(m^2\right)=\tau\left(n^2\right)\,.$$ This proves that $n-\phi(n)>\tau\left(n^2\right)$ for any odd natural number $n$ with at least three distinct prime divisors.
Now, we shall prove that $n=21$ and $n=25$ are the only solutions in $\mathbb{N}$ to $n=\phi(n)+\tau\left(n^2\right)$. It is clear that $n\neq 1$ and that $n$ is odd. From the paragraph above, $n$ has at most two distinct prime divisors. If $n$ has one prime divisor, say $n=p^a$, then the required condition gives $p^{a-1}=2a+1$, which leads to $p=5$ and $a=2$, whence $n=25$. If $n$ has two prime divisors, say $n=p^aq^b$ with $2<p<q$, then we have $$2(2a+1)q^{b-1}\leq 2p^aq^{b-1}<p^{a-1}(q-1)q^{b-1}+p^aq^{b-1}=(2a+1)(2b+1)\,.$$ That is, $q^{b-1}<\frac{2b+1}{2}$, which means $b=1$. Hence, we have $$2p^a=2p^aq^{b-1}<(2a+1)(2b+1)=3(2a+1)\,.$$ This gives $p=3$ and $a=1$. Therefore, $n=3q$. Ergo, $$3q-2(q-1)=n-\phi(n)=\tau\left(n^2\right)=9\,,$$ leading to $q=7$, whence $n=21$.

Answer 2

Here's a sketch.

We know this fails for primes.

For composite $n$, $\phi(n) \le n-\sqrt{n}$.

For any $n$, we have $$ \tau(n) < k n^\frac{1}{5} $$ for all $k>0$, $n$ sufficiently large ($\tau(n)$ is the number of divisors of $n$).

Hence, $\phi(n) + \tau(n^2) < n -\sqrt{n} + k n^\frac{2}{5} < n$ for $n$ sufficiently large.

We check all composite $n$ up to that bound, and we know all solutions.

(There are two.)