# Thread: For any integer n

1. ## For any integer n

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

2. Originally Posted by ogajawasungu
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 $\sigma(p^m) = m+1$ so taking $k=0$, $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?

3. Sorry, the question should read; find all integers n such that σ(n)+φ(n)=2n

4. Originally Posted by ogajawasungu
Sorry, the question should read; find all integers n such that σ(n)+φ(n)=2n
That's a huge typo!

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

6. Originally Posted by hollywood
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.
Take $n = pq$ with $p$ and $q$ prime. $\varphi{(n)} = (p - 1)(q - 1)$, $\sigma{(n)} = p + q + pq + 1$

So $\varphi{(n)} + \sigma{(n)} = (p - 1)(q - 1) + p + q + pq + 1 = pq - p - q + 1 + p + q + pq + 1$ $= 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 )

7. Originally Posted by Bacterius
...assuming the validity and existence of the GFP (Generalized Forgotten Proof )
That GFP sounds very useful! I'll have to use it in future proofs in coordination with TAMH.

(Then a Miracle Happens, for the uninitiated.)