5
$\begingroup$

I am asked to find all naturals $n$ such that $\sigma(n) + \phi(n) = n\tau(n)$ where $\sigma, \phi, \tau$ are the sum of divisors, euler totient, and divisor counting functions respectively. ($\sigma$ gives the sum of divisors of $n$ and $\tau$ gives the number of divisors of $n$)

I have noticed that if $n = 1 \text{ or it is prime,}$ then the equation holds, and from running a quick Python check for the first 10,000 naturals, these seem to be the only solutions. However, I am unsure how I can prove that there are no other solutions.

I am aware that $\phi$ and $\sigma$ are multiplicative functions, that is that if $m,n \in \mathbb N, gcd(n,m) = 1$ then $\sigma(mn) = \sigma(n)\sigma(m)$ and $\phi(mn) = \phi(n)\phi(m)$

I've found that if $n = p_1^{a_1}\dots p_k^{a_k} $ for distinct primes $p_1,\dots,p_k$, then $\tau(n) = \prod_{i=1}^{k}(a_i+1)$ which seems to imply that $\tau$ is also a multiplicative function.

Thus we have that if $n,m \in \mathbb N, gcd(n,m) = 1$ then:

$\sigma(mn) + \phi(mn) = \sigma(n)\sigma(m) + \phi(n)\phi(m)$ and $nm\tau(nm) = nm\tau(n)\tau(m)$, so if $nm$ satisfies the condition then:

$\sigma(m)\sigma(n) + \phi(m)\phi(n) = nm\tau(n)\tau(m)$

From this equation it is clear that for $n,m \mathbb N \backslash \{1\} $, $n,m,nm$ cannot all be solutions. Specifically, if $nm$ is a solution then at most one of $n,m$ is also a solution.

Assuming that $n$ is a solution we get that:

$\sigma(n)\sigma(m) + \phi(n)\phi(m) = m\tau(m)(\sigma(n) + \phi(n))$

$\Rightarrow \sigma(n)(\sigma(m) - m\tau(m)) + \phi(n)(\phi(m) - m\tau(m)) = 0$

Now note $\sigma(m) - m\tau(m) < 0$ and $\phi(m) - m\tau(m) < 0$

$\Rightarrow LHS < 0 $, a contradiction. Hence we conclude that $nm$ can satisfy the equation only if $n,m \in \mathbb N \backslash\{1\}$ don't.

This then implies that if $n$ is composite and satisfies the equations then every prime factor $p$ must satisfy $p^2 \mid n$, i.e. n is not square free.

And now I don't know how to proceed. I don't know what more I can show and I don't know how I can show that the primes are the only solutions other than $1$. Any help would be greatly appreciated, thank you!

$\endgroup$
  • $\begingroup$ That identity is not true at $n=1$, since $f(1) = 1$ when $f$ is $\phi$, $\sigma$, or $\tau$. $\endgroup$ – KCd Nov 19 '17 at 22:30
5
$\begingroup$

Let $n$ be composite, say $n=ab$ with $1<a<n$. Then by rearranging the equation, $$ n-1\ge \phi(n) =n\sum_{d\mid n}1-\sum_{d\mid n}d=\sum_{d\mid n}(n-d)\ge (n-1)+(n-a),$$ which is absurd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.