Problems & Puzzles:
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
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
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
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.
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
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..."