For any integer n show that there exist integers k and j such that φ(k)+σ(j)=n

Printable View

- May 7th 2010, 07:42 AMogajawasunguFor any integer n
For any integer n show that there exist integers k and j such that φ(k)+σ(j)=n

- May 10th 2010, 07:30 AMSwlabr
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? - May 10th 2010, 08:01 AMogajawasungu
Sorry, the question should read; find all integers n such that σ(n)+φ(n)=2n

- May 10th 2010, 10:06 AMchiph588@
- May 10th 2010, 05:57 PMhollywood
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 - May 10th 2010, 08:07 PMBacteriusQuote:

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 :D) - May 10th 2010, 09:25 PMundefined