Prove the statements below:

a) An integer $n$ is prime if and only if $\sigma(n)+\phi(n)=n \tau(n)$ [Hint: Derive $\sum_{d|n}{\sigma(d)\phi(\frac{n}{d})}=n\tau(n)$]

b) An integer $n$ is prime if and only if $\phi(n)|(n-1)$ and $(n+1)|\sigma(n)$

For part a), I manage to derive the equation given in the hint, but I still don know to prove the backward direction.

For part b), the forward direction is straight forward. But I stuck at the backward direction. There is one result '$\phi(n)|(n-1)$ implies that $n$ is square-free' where I have proven. I don know whether it is useful here.

Can anyone guide me?


I see an easier way to prove (a). Suppose first that $n=p$ is prime. Then $\tau(p)=2$, $\sigma(p)=p+1$, $\phi(p)=p-1$, so that $\sigma(p)+\phi(p)=(p+1)+(p-1)=2p=p\tau(p)$.
Conversely, assume that $n$ is not prime. Then we have $\phi(n)<n-1$ and $\sigma(n)\le 1+(\tau(n)-1)n$. This gives $$ \phi(n)+\sigma (n)<(n-1)+1+(\tau(n)-1)n=\tau(n)n. $$

  • $\begingroup$ How you obtain $\sigma(n) \leq 1 +( \tau(n) -1)n$? $\endgroup$ – Idonknow Sep 19 '13 at 10:30
  • $\begingroup$ @Idonknow $n$ has $\tau(n)-1$ divisors that are $> 1$, and all of them are $\leqslant n$. So $$\sigma(n) = \sum_{d\mid n} d = 1 + \sum_{\substack{d\mid n\\d>1}} d \leqslant 1 + (\tau(n)-1)\cdot n.$$ $\endgroup$ – Daniel Fischer Sep 19 '13 at 11:14

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.