Solving $\tau(n)+\phi(n)=n$ for $n\in\mathbb{N})_{\ge 1}$.

Question

Let $\tau(n)$ denote the number of divisors of a positive integer $n$, and let $\phi(n)$ be Euler's totient function, i.e. the number of positive integers less than and coprime to $n$. I'd like to find all $n$ such $$ \tau(n)+\phi(n)=n.$$

• The case when $n=p$ for $p\in\mathbb{P}$ is easy. We have $\tau(n)=2$, $\phi(n)=p-1$ and the equation is equivalent to $$ 2+p-1=p+1=p,$$ which is impossible.
• The case of $n=p^k$, where $k\in\mathbb{N}_{\ge 2}$ is already more complicated. We have $\tau(p^k)=k+1$ and $\phi(p^k)=p^k(1-1/p)$, hence the equation is equivalent to $$ k+1+p^k\left(1-\frac{1}{p}\right)=p^k,$$ which can be rearranged into $$ k=p^{k-1}-1=p^{k-1}-1^{k-1}=(p-1)(p^{k-2}+p^{k-3}+\ldots+1).$$ For example, for $k=2$ this is $2=p-1$, and $p=3$. It's easy to check that $n=3^2=9$ satisfies the conditions. For $k=3$, we have $3=p^2-1$, and $p=2$. Hence $n=2^3=8$. $k=4$ gives $4=p^3-1$, and unfortunately there's no solution.
• When $n=p_1\cdot p_2^k$ with $p_1,p_2$ distinct primes, we have $\phi(p_1p_2^k)=\phi(p_1)\phi(p_2^k)$. As $\tau(p_1p_2^{k})=2+k+1=k+3$, $\phi(p_1)=p_1-1$ and $\phi(p_2^k)=p_2^k(1-1/p_2)$, the equation transforms into $$k+3+p_1-1+p_2^k\left(1-\frac{1}{p_2}\right)=p_1p_2^k,$$ which, after little bit of rearranging gives $$ k+2+p_1+p_2^k-p_2^{k-1}=p_1p_2^k.$$ For $k=1$, this is $$1+2+p_1+p_2-p_2^{0}=p_1p_2, $$ or $$ 2+p_1+p_2=p_1p_2,$$ which does not help very much.

I have no clue about the approach to the general case. I'm not even sure my current approach is useful at all.

Any hints greatly appreciated.

Answer 1

Clearly $n > 1$ if $\tau(n) + \phi(n) = n$, so such an $n$ has a prime divisor. And by your first point, it is composite. Since $n$ has exactly one divisor that is coprime to $n$, the condition is that among the numbers $\leqslant n$ that are not coprime to $n$, all but one divide $n$.

Let $p$ be the smallest prime divisor of $n$. If $p > 2$, then $2p < n$, and $\gcd(2p,n) = p > 1$, but $2p\nmid n$. Since $4p \nmid n$ and $\gcd(4p,n) = p > 1$, it follows that $n = 3p$, so $p = 3$ and $n = 9$.

So let's look at the case $2 \mid n$. If $n$ is a power of $2$, say $n = 2^k$ then $(k+1) = 2^{k-1}$ holds only for $k = 3$, so $8$ is the only power of $2$ with this property. Thus, in the following we can assume that $n$ has other prime divisors than $2$. Let $q$ be the smallest odd prime divisor of $n$, and write $n = 2^k\cdot q^m \cdot r$, with $\gcd(2q,r) = 1$. If we had $r > 1$, then $2^{k+1}$ and $q^{m+1}$ would be two numbers $< n$ that aren't coprime to $n$, yet neither divides $n$. So $n = 2^k\cdot q^m$. If $q > 3$ or $m > 1$, then $2^{k+1}$ and $2^{k+2}$ would both be $\leqslant n$, not coprime to $n$, and not divide $n$. So we must have $n = 2^k\cdot 3$. If $k \geqslant 2$, then $9$ and $10$ are both less than $n$, not coprime to $n$, and don't divide $n$. Hence it follows that $k = 1$.

Thus the complete list of such $n$ is $6,8,9$.

Answer 2

$$n-\tau(n) = \sum_{a=2}^n 1_{a \,\nmid \, n}$$ $\sum_{a=2}^n 1_{a \,\nmid \, n} = \phi(n) = 1+\sum_{a=2}^n 1_{(a,n)=1}$ means there is exactly one $a \in [2,n]$ such that $(a,n)\ne 1$ and $a\nmid n$.

Take a prime $p | (a,n)$. Thus $n = p d$ and for any $b = p r,r \in [2,d], (r,d)=1$ we have $(b,n)\ne 1$, $b\nmid n$ ie. $\phi(d)-1$ possibilities. Therefore $\phi(d)-1 = 1$ and $d = 3$ or $4$ or $6$

Hence $n= 3p$ or $4p$ or $6p$ and we obtain the complete list of solutions easily.