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


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




Records   |  Conjectures  |  Problems  |  Puzzles