7
$\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$
1
  • $\begingroup$ That identity is not true at $n=1$, since $f(1) = 1$ when $f$ is $\phi$, $\sigma$, or $\tau$. $\endgroup$
    – KCd
    Commented Nov 19, 2017 at 22:30

1 Answer 1

6
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .