# Proving an identity involving arithmetic functions holds only for primes

Prove the statement $\phi(p) + \sigma(p) = p \cdot \tau(p)$ if and only if $p$ is prime.

Any tips how can I prove both sides? Thanks.

-
@primemiss that's correct: $(p-1) + (p+1) = p*2.$ – user2468 Sep 1 '12 at 18:38

To show that the equation holds when $p$ is prime is a straight calculation. If $p$ is prime then $\varphi(p)=?$. And $\sigma(p)=?$. And $p\,\tau(p)=?$. Fill in the question marks and you will have a proof.

For the other direction, it is useful to get some experience. So compute the left-hand side, the right-hand side, for $p=1$, $4$, $6$, $8$, $9$, maybe even a few more. What do we find? Well, $1$ is special. Let's call our test number $n$, not $p$. We observe that if $n \gt 1$, and $n$ is not prime, then it looks as if $n\tau(n) \gt \varphi(n)+\sigma(n)$.

And there is good reason for that. The expression $n\tau(n)$ "adds up" an $n$ for every divisor of $n$. The expression $\sigma(n)$ "adds up" $d$ for every divisor $d$ of $n$. Mostly these divisors are $\lt n$. One of them is $1$, tiny. At least one more is $\lt n$. So if $n\gt 1$ is not prime, then $n\tau(n)-\sigma(n)\gt (n-1)+1$. Throwing in $\varphi(n)$, which is $\lt n-1$, won't help.

For concreteness, take for example $n=15$. Then $n\tau(n)=15+15+15+15$. And $\sigma(n)=1+3+5+15$. Just as many terms (that's always true), but all but one of the terms for $\sigma(n)$ is too small. Note that the term $1$ put $\sigma(n)$ well behind $n\tau(n)$, and the term $3$ put it further behind. Can $\varphi(n)$ added to $\sigma(n)$ make it catch up to $n\tau(n)$? No, $\varphi(n)$ is too small. Let's do it for $n=25$. We have $n\tau(n)=25+25+25$. And $\sigma(25)=1+5+25$, way behind. Do it yourself for say $n=14$, and you will be ready to write a proof.

Once you internalize the informal idea I have been trying to describe, writing a formal argument should not be very hard. The final argument is quite short. It can be done in a couple of lines! I will post it in a day or so.

Added: As promised, here is a proof. Suppose that $n$ is composite. Then $n$ has at least $3$ divisors. One of them is $1$. Another is say $d$, where $1\lt d\le n-1$. The remaining $\tau(n)-2$ divisors are all $\le n$. So $$\sigma(n)\le 1+(n-1)+n(\tau(n)-2)=n\tau(n)-n.$$ But $\varphi(n)\lt n$, and therefore $$\varphi(n)+\sigma(n)\lt n+(n\tau(n)-n)= n\tau(n).$$ Consequently, $\varphi(n)+\sigma(n)\ne n\tau(n)$.

-
When $n = 14$, we have $n\tau(n) = 14 + 14 +14$ and $\sigma(14) = 1 + 7 + 14$. If p is a prime then $n\tau(n)$ and $\sigma(n)$ have tha same number number of terms and what makes them equal is by adding $\phi(n)$ to $\sigma(n)$? Am I in the right path? How can I write it in formal proof? – primemiss Sep 1 '12 at 19:21
It doesn't make them equal. The $\sigma$ guy is behind by $(14-1)+(14-7)$, which is more than $14$, so adding $\varphi$, which is $\lt 14$, is not enough. If you think about the issue, you will see (and then be able to prove) that this always happens for composite $n$. As I wrote in the post, after seeing what's going on, I think you will be able to write a proof. I want to wait a little while, a few hours at least, so that you can discover the proof yourself. – André Nicolas Sep 1 '12 at 19:30
Let me try again, if n is "prime" then $n\tau(n) = n+n$ and $\sigma(n)=1+n$ so it is behind $(n-1)$ so by adding $\phi(n)$ is enough to make them equal. If n is "composite" then $n\tau(n)$ will generate more than two terms thus will make it sum farther than $\sigma(n)$ that by adding $\phi(n)$ will not be enough. – primemiss Sep 1 '12 at 19:53
Once recognized, you of course need to formalize this "is behind" handwaving (as helpful as it was to discover this). If $1<d<n$ is a nontrivial divisor of $n$, then $\sigma(n)$ is by definition the sum of $\tau(n)$ divisors, one of them is $1$, another is $d$ and all others are $\le n$, hence $\sigma(n)\le 1 + d + (\tau(n)-2)\cdot n$. – Hagen von Eitzen Sep 2 '12 at 8:18

When attempting a proof, break it down one step at a time. First of all, "if and only if" means that you actually have two proofs:

1) If $p$ is prime you need to show that the equation holds. This is very straight-forward: what are the values of each of the functions in the equation when $p$ is prime?

2) If the equation holds true, then you need to show that $p$ is prime. What does it mean for a number to be prime? When approaching this kind of proof, you need to look at the definition of what you are trying to prove. This will give you some cluse as to what to do next.

I hope these hints help you get started. If you get stuck along the way, feel free to edit your question with more details so that we can help you from there.

-
(1) is the converse right? Yes it's straight forward. I'm currently working on the if-statement but still confuse. Thanks anyway! :) – primemiss Sep 1 '12 at 18:34
@primemiss What are you confused about? Please edit your question with details about what you have tried so far and where you are stuck. – Code-Guru Sep 1 '12 at 18:38