Problems & Puzzles: Puzzles

Puzzle 343. One more Faride's question Faride Firoozbakht wrote: I guess that: "If n>2 and m is a solution of the equation sigma(x)-phi(x)= n, then m isn't greater than (n-1)^2/4. " Q1: can you prove it? (I only know that if p=(n-1)/2 is prime then p^2 is a solution for (*) because sigma(p^2)-phi(p^2)=(p^3-1)/(p-1)-p(p-1)=2p+1=n.)

---

The solution was found and only by Luke Pebody.

***

Theorem: If n>2 and integer m satisfies sigma(m)-phi(m)=n then m<=(n-1)^2/4

Proof:

Case I: m=1

Then n=sigma(m)-phi(m)=0 is not more than 2.

Case II: m is prime

Then n=sigma(m)-phi(m)=(m+1)-(m-1)=2 is not more than 2.

Case III: m has at least one non-trivial divisor.

Let m=pq where 1<p<m.
Then sigma(m) is the sum of all of the distinct factors of m. Thus sigma(m)>=m+p+1.

Phi(m) counts the number of integers smaller than or equal to m that are coprime to m.
It certainly is no greater than the number of integers smaller than or equal to m that are not divisible by p. Thus phi(m)<=m-q.

Thus n=sigma(m)-phi(m)>=p+q+1.

Finally, the arithmetic mean of two numbers is always greater than their geometric mean, so Sqrt(m)=Sqrt(pq)<=(p+q)/2<=(n-1)/2. Squaring both sides, m<=(n-1)^2/4.
 

Faride's comment on Pebody's proof:

"...the proof seems to be rather interesting and beautiful. Something that hadn't come to my mind. Pebody is indeed a smart mathematician..."
 

***

 

 

---