Problems & Puzzles:
= x^2 - (1/n)*x
Farideh Firoozbakht sent the following puzzle:
Related to the equation:
phi(x)*sigma(x) = x^2 - (1/n)*x, n=integer.
Q1. Prove that has solution iff n is prime
Q2. Prove that if n=p is prime all solutions
of the equation are all natural powers of p (p, p^2, p^3, ....
Contributions came from Steve Zook and Fred Schneider
Question 2 Sufficiency proof:
For p prime and a an integer, phi(p^a) = (p-1)*p^(a-1) and sigma(p^a)
= (p^(a+1)-1)/(p-1). Thus phi(p^a)*sigma(p^a) =
(p-1)*p^(a-1)*(p^(a+1)-1)/(p-1) = p^(a-1)*(p^(a+1)-1)
For n = p and x = p^a, x^2-(1/n)*x = (p^a)^2-(1/p)*p^a =
p^(2*a)-p^(a-1) = p^(a-1)*(p^(a+1)-1)
Therefore phi(x)*sigma(x) = x^2-(1/n)*x when n = p prime and x = p^a
for any a >= 1.
Hola Senor! ...
Let x1 = p1^a1 where p1 is a prime and a1 is a positive integer
phi(x1) = (p1-1)*p1^(a1-1)
sigma(x1) = (p1^(a1+1)-1)/(p1-1)
Let ps(x) = phi(x) * sigma(x)
ps(x1) simplifies to : (p1^(a1-1)) * (p1^(a1+1)-1) = x1^2 - x1/p1.
So where x is a prime power, n (from the problem) = p1.
Let x2 = p2^a2 where p2 is prime and is greater than p1, and a2 is
again a positive integer.
Similarly, ps(x2) = x2^2 - x2/p2
Let y2 = x1 * x2;
Because f(ab) = f(a)*f(b) (where f is function phi or sigma and
ps(y2) = ps(x1) * ps(x2)
= (x1^2 - x1/p1) * (x2^2 -x2/p2)
= y2^2 - x2*y/p1 - x1y/p2 + y/(p1*p2)
After rearranging the terms we have:
= y2^2 - ((p1^(a1+1) + p2^(a2+1) -1)/(p1*p2) ) * y
n = (p1*p2) / (p1^(a1+1) + p2^(a2+1) -1)
p1 and p2 are primes, specifically positive integers. So clearly,
the values of
n is maximxed when a1 = a2 = 1
giving us: (p1*p2) / (p1^2 + p2^2 -1)
Further, for postive integers, the value is maximized when p1 == p2
this expression will evaulate to p^2/(2*p^2-1).
But p1 and p2 are not equal so the maximal value would be 1/2 for n
Now we know that numbers of y2's form can not have an integral n.
We can use that upper bound of 1/2 for an inductive proof to show
is never an integer for numbers which are product of more than 2
Let y(m) = x1 * x2 ... * x(m) = p1^a1 * p2^a2 .. * p(m)^a(m)
where p1 < p2 ... < p(m),p(i) are prime numbers and a(i) are
ps(y(m)) = y(m)^2 - 2*y(m) [ n is set to an upper bound of 1/2 ]
Let x(m+1) = p(m+1)^a(m+1) [ p(m+1) is a prime > p(m) and a(m+1) is
a positive integer ]
and y(m+1) = y(m) * x(m+1)
ps(y(m+1)) = ps(y(m)) * ps(x(m+1)) =
(y(m)^2 - 2*y(m)) * ( x(m+1)^2 - x(m+1)/p(m+1) ) =
y(m+1)^2 - (2 * x(m+1) + (y(m) -2)/(p(m+1) ) * y(m+1)
n = 1/(2 * x(m+1) + (y(m) -2)/(p(m+1))
x(m+1) is a prime power and (y(m) -2)/(p(m+1) is always a positive
Therfore: If the relation is not true for the m-th case, it's not
true for the (m+1)-th
It was shown earlier that an integral n is not possible.
So by induction, n can never be an integer (much less prime)
for integers that aren't prime powers.
One final note: one see that even if n is set to a higher upper
bound less than 1
(for instance, by plugging in 1/(9/10)=10/9 for 1/(1/2)=2 in the
expression for n above),
n at the next iteration can not be greater than one, much less a
Antoine Verroken wrote (Set. 09) & Farideh slightly corrected:
About Q1. I proved that if the equation has solution then n
is square-free and each
solution of the equation is a multiple of n.
Proof : phi(x) * sigma(x) = x^2 – x / n (1)
Suppose x = a^m * b^r * c^ q (a,b, c primes m,r & q are natural
we can take an arbitrary number of distinct prime factors for x) be
for (1); then
phi(x) = a^m * b^r * c^q * ( a-1)*(b-1)*(c-1) / ( a*b*c )
and sigma (x) = [a^( m + 1 ) – 1] * [ b^( r + 1 ) – 1]*[ c^( q + 1 )
– 1] /
[( a – 1 ) * ( b – 1 ) * ( c – 1 )]
(1) --> a^m * b^r *c^q * [a^( m + 1 ) – 1]*[ b^( r + 1 ) – 1]*[ c^(
q + 1 ) – 1] /
( a*b*c ) = a^ ( 2*m ) * b^ ( 2*r ) * c^ ( 2*q ) – a^m * b^r * c^q /
or [a^( m + 1 ) – 1]*[ b^( r + 1 ) – 1]* [ c^( q + 1 ) – 1] =
a^ ( m + 1 ) * b^( r + 1 ) * c^( q + 1 ) – a*b*c / n
Similarly if x = p1^a1*p2^a2*...*pk^ak is a solution for (1) then we
(p1^(a1+1) - 1)*(p2^(a2+1) - 1)* ... * (pk^(ak+1) - 1) =
p1^(a1+1) *p2^(a2+1)* ... * pk^(ak+1) - (p1*p2* ...*pk) / n (**)
because (p1*p2* ...*pk) / n must be an integer, n must be
square-free and x
is a multiple of n.
About Q2. I proved that if n = a is prime then numbers of the
form a^m, (m is a natural
number) are in the set of solutions of (1).
x = 1 phi(1) = 1 ; sigma(1) = 1 ; ( 1 ) à 1 * 1 = 1 – 1 / n à
x = a^m (a is prime and m is a natural number)
phi(x) = a^m * (1 – 1 / a) = a^(m – 1) * (a – 1)
sigma(x) = 1 + a + a^2 + … + a^m
(1) --> a^( m – 1 ) * ( a – 1 ) * ( 1 + a + a^2 + … + a^m ) = a^ (
2*m ) – a^m / a
or a^m * ( a – 1 ) * ( 1 + a + a^2 + … + a^m ) = a^m * [ a^( m + 1 )
– 1 ]
a^m * ( a – 1 ) * (a^( m + 1 ) – 1) / ( a - 1) = a^m * [ a^( m + 1 )
– 1 ]
and this is an equality.
So all numbers of the form a^m ( m is a natural number) are in the
set of solutions.