Problems & Puzzles: Puzzles

Puzzle 76.- z(n)=sigma(n) + phi(n) - 2n

(An example of an email-born-puzzle, by Jud McCranie & Carlos Rivera, November 1999)

It's well known that if n = p^a.q^b.  etc., then

• sigma(n)= (p^(a+1)-1)/(p-1)*(q^(b+1)-1)/(q-1)* etc
• phi(n) = (p-1)*p^(a-1) * (q-1)*q^(b-1)* etc 

Jud's observation (9/11/99):

"When p is prime sigma(p) = p+1 and phi(p) = p-1, so sigma(p)+phi(p) = 2p, �.  I was wondering if sigma(n)+phi(n)=2n ever happens when n isn't prime�"

My reply (10/11/99):

"Then it seems interesting define z(n) as z(n)=sigma(n) +phi(n)-2n. Obviously z(p)=0. Less obvious is that z(p^2)=1 and z(p*q)=2. Can you see other properties of z(n)?"

Jud responded:

(11/11/99) sigma(Perfect)=2n, then z(Perfect)=phi(Perfect)

(12/11/99): z(p^3)=p+1, z(p^4)=p(p+1)+1, this must generalize z(p^k)=p(p(p�.+1)+1)+1 opening and closing (k-3) parentheses

(12/11/99): z(pqr)=2(p+q+r), p,q,r distinct primes

Later I saw that z(p^k)=1+p+p^2+p^3+�+p^(k-2) and then Jud reminded to me that sigma(p^k)= 1+p+p^2+p^3+�+p^k, and also that sigma and phi are multiplicative functions, that is to say: sigma(x.y)=sigma(x).sigma(y) and phi(x.y)=phi(x).phi(y), if gcd(x,y)=1.

With these hints I deduced (the known fact) that phi(p^k)=(p-1)*p^(k-1) and consequently phi(Perfect)=2^(p-2).(2^p-2)

In B37, p. 92, "Unsolved Problems in Number theory", R. K. Guy, I found that "Subbarao also notes that �. p.sigma(p)=2 mod phi(p), and also for n=4, 6 & 22" (*), and Jud found (**) also that "6n^2/pi^2 < phi(n)*sigma(n) < n^2".

This is enough! Now, the questions are:

1.      sigma(n)+phi(n)=2n ever happens when n isn't prime�?�(This is the very original Jud's question)

2.      Does exists a formula to calculate directly z(n) for the general case n=p^a.p^b. etc

3.      Find composite numbers, other than 4, 6 & 22, such that applies the Subbarao relation.

Notes
_________

(*)This is also mentioned at:
http://www.treasure-troves.com/math/TotientFunction.html)
(**) Algorithmetic Number Theory, by Bach and Shallit

Solution

Chris Nash has solved (20/12/99) the question 1 of this puzzle and consequently and in certain unexpected manner (applying the M�bius function to each divisor of n - see the equation 7 ) the question 2 also... I must confess that I'm completely astonished for the beauty of this reasoning and in particular for the unknown (for me) trick of the so called "M�bius inversion formula"....phew!!!

1  Definitions

2  Solution of Puzzle 76

We first note the following relations which follow directly from the definitions of f(n) and s(n):

In particular, this means n cannot have two or more distinct prime factors. If n had distinct prime factors p and q, choose d = n/pq and we have a contradiction with (8). Hence n must be a power of a prime.

Similarly, if n = p^r for some r > 1, choose d = 1 and again we have a contradiction with (8).

Finally it is easy to demonstrate that, if n is prime, f(n) = n-1 and s(n) = n+1.

Hence z(n) = 0 if and only if n = 1, or n is prime

***

Chris Nash has also solved (21/12/99) the question 3 ..."Using an elegant function [z(n)] discussed by Carlos Rivera and Jud McCranie at
http://www.sci.net.mx/~crivera/puzzles/puzz_076.htm that it has been possible to prove no other composite solutions exist to the Subbarao relation. The full proof is available for download in Adobe Acrobat PDF format at http://pages.prodigy.net/chris_nash/puzzle76.pdf while an HTML"approximation" generated using "tth" is also available at
http://pages.prodigy.net/chris_nash/puzzle76.html"

***

Farideh Firoozbakht wrote on Jan-2015:

I found the following nice proof for "sigma(n) + phi(n) > 2n, where n is a composite number". 
 

The proof is simpler than the Chris Nash's proof without using Mobius inversion formula
 

Theorem :  For all composite numbers n, sigma(n) + phi(n) > 2n.
 

Proof : 
sigma(n) = sum (d | d|n, 1 <= d <= n)  =>  sigma(n) - n = sum(d | d|n, 1 <= d < n)         (I)
n = sum (phi(d) | d|n, 1 <= d <= n)  =>  n - phi(n) = sum (phi(d) | d|n, 1 <= d < n)          (II)  
(I) & (II) => (sigma(n) - n) - (n - phi(n)) = sum (d - phi(d) | d|n, 1 <= d < n) => 
sigma(n) + phi(n) - 2n = sum (d - phi(d) | d|n, 1 < d < n)   (since, 1 - phi(1) = 0)
 

Now if n = 1 or n is a prime number then there is no such d and sigma(n) + phi(n) = 2n

and if n is a composite number then there exists at least one divisor d1 of n where 
 

1 < d1 < n  hence, sigma(n) + phi(n) - 2n = sum (d - phi(d) | d|n, 1 < d < n) >= d1 - phi(d1) > 0. And the proof is completed.
 

We can easily generalize this proof for the Jordan's totient function J_k(n) 

and prove that for all composite numbers n, J_k(n) + sigma_k(n) > 2*n^k.

I think the theorem is a nice result of the well known theorem
" for all n,  n = sum (phi(d) |  d|n, 1 <= d <= n) ".

***