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.
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.
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 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.