For any integer n

Printable View

May 7th 2010, 07:42 AM
ogajawasungu

For 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 AM
Swlabr

Quote:

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?
May 10th 2010, 08:01 AM
ogajawasungu

Sorry, the question should read; find all integers n such that σ(n)+φ(n)=2n
May 10th 2010, 10:06 AM
chiph588@

Quote:

Originally Posted by ogajawasungu

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

That's a huge typo! (Rofl)
May 10th 2010, 05:57 PM
hollywood

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 PM
Bacterius

Quote:

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

Quote:

Originally Posted by Bacterius

...assuming the validity and existence of the GFP (Generalized Forgotten Proof :D)

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