Find all postive integers $n$ such that $n+\varphi{(n)}=2\tau{(n)}$

203 Views Asked by At

Let $n$ be a positive integer such that $$n+\varphi{(n)}=2\tau{(n)}$$ where φ is the Euler's totient function and τ is the divisor function i.e. number of divisors of an integer.

since $$4+\varphi(4)=4+2=6=2\cdot 3=2\tau(4)$$ $$6+\varphi(6)=6+2=8=2\cdot 4=2\tau(6)$$ maybe $n=4,6$ is only solution? and How prove it, I asked a similar question earlier, but it seemed different. Find all postive integers $n$ such that $n+\tau{(n)}=2\varphi{(n)}$

1

There are 1 best solutions below

0
On

If $n+\phi(n)=2\tau(n)$, then we have that

$$n<2\tau(n)$$

Let $n=p_1^{a_1}\cdots p_s^{a_s}$ be the prime factorization of $n$. Then

$$\prod_{i=1}^s p_i^{a_i} < 2\prod_{i=1}^s (a_i+1) \implies \prod_{i=1}^s \left(\frac{p_i^{a_i}}{a_i+1}\right) < 2.$$

We note that

$$p_i^{a_i} = ((p_i-1)+1)^{a_i} \geq 1+(p_i-1)a_i \geq 1+a_i,$$

(where we have obtained the first inequality from the binomial theorem), so each of the terms in the product are $\geq 1$, which implies that they all must be less than $2$. We see that, if $p_i>3$,

$$p_i^{a_i} \geq 1+(p_i-1)a_i \geq 1+4a_i > 2a_i+2,$$

which means the terms are $>2$ if $p_i>3$, a contradiction. Thus, $p_i$ is $2$ or $3$. If $p_i=2$, it can easily be seen by inspection that the terms remain $<2$ only for $a_i=1$ or $a_i=2$, and if $p_i=3$, it can be seen that the terms are $<2$ iff $a_i=1$. Thus, the only possible answers are

$$2^x 3^y$$

where $0\leq x\leq 2$ and $0\leq y \leq 1$. By simple case-checking, we see that the only ones of these which work are $1$, $4$, and $6$, finishing the proof.

Remark: This problem is substantially easier than the question of $n+\tau(n)=2\phi(n)$, as that problem relies on the bound that $n/2>\phi(n)$ for most $n$, while this one relies on the bound that $n/2>\tau(n)$ for most $n$. While the second only has finitely many exceptions, the first is false infinitely often.