For any integer n show that there exist integers k and j such that φ(k)+σ(j)=n
In words, show that for all n there exists integers k and j such that the number of divisors of j plus the number of numbers coprime to and less than k is n.
So, I would note that $\displaystyle \sigma(p^m) = m+1$ so taking $\displaystyle k=0$, $\displaystyle j=p^{n-1}$.
However, this is only for the natural numbers and zero...not the whole integers. You can't get a negative number of divisors!
It is also a somewhat boring result - why the Euler totient function if we can just forget about it?...
Have you perhaps missed out something from the question?
If p is prime, then sigma(p)=p+1 (since there are only the two factors, 1 and p). Also, phi(p)=p-1 since all of the integers from 1 to p-1 are coprime to p, so sigma(p)+phi(p)=2p.
I think it's probably true, but I can't see a way to prove that there are no composite n with sigma(n)+phi(n)=2n.
- Hollywood
Take $\displaystyle n = pq$ with $\displaystyle p$ and $\displaystyle q$ prime. $\displaystyle \varphi{(n)} = (p - 1)(q - 1)$, $\displaystyle \sigma{(n)} = p + q + pq + 1$Originally Posted by hollywood
So $\displaystyle \varphi{(n)} + \sigma{(n)} = (p - 1)(q - 1) + p + q + pq + 1 = pq - p - q + 1 + p + q + pq + 1$ $\displaystyle = 2pq + 2 = 2n + 2 \color{red}{\ \neq 2n}$
Oops, I just wiped out all semiprimes
I believe there is a general proof that can be built around this with infinitely many prime factors instead of a semiprime. I've seen it but unfortunately forgot it, I'll have to check it out some time.
Conclusion : only prime numbers satisfy this statement, along with 1, assuming the validity and existence of the GFP (Generalized Forgotten Proof )