# How to prove a number is prime

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.$$
• How you obtain $\sigma(n) \leq 1 +( \tau(n) -1)n$? – Idonknow Sep 19 '13 at 10:30
• @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.$$ – Daniel Fischer Sep 19 '13 at 11:14