UPhi

[Max]

On 4/29/06, koh <zbi74583 at boat.zero.ad.jp> wrote:

>     %S A000001 1,3,15,216,255,1728,65535,182880,1226400,3456000,14738400,174182400,4294967295,
>
>     %N A000001 Numbers such that UnitaryPhi(2*UnitaryPhi(n))=n.
>     %C A000001 Odd terms are of the form Product_{0<=i<=m} F_i, 0<=m<=4, where F_i is Fermat prime 2^(2^i)+1

n=1 is not of the form Product_{0<=i<=m} F_i, 0<=m<=4.
And there are 6 odd terms not 5 as one may conclude from the statement above.

>     I wonder if odd terms are all.

They are.

Let n>1 be an odd number such that UnitaryPhi(2*UnitaryPhi(n))=n.
Let m=2*UnitaryPhi(n).
Since UnitaryPhi(m)=n is odd, m must be a power of 2.
Hence, all prime powers in the factorization of n must be of the form
p^d = 2^k + 1. There are two cases:
1) d=1, then p is Fermat prime
2) d>1, then p^d=9 (because of Catalan's conjecture, proved in 2002).

Consider two cases depending on whether n is divisible by 9.

Suppose that n is a product of distinct Fermat primes, i.e., n=\prod_i
(2^(2^k_i)+1).
Then m = 2^t and n=UnitaryPhi(m)=2^t-1 where t=1+\sum_i 2^k_i.
If q is an odd divisor of t, then 2^q-1 is a divisor of n which is
co-prime to any Fermat number. Hence, t must be a power of 2, i.e.,
t=2^s. Then n is a product of Fermat numbers:
n=2^(2^s)-1=(2^(2^(s-1))+1)*(2^(2^(s-2))+1)*...*(2^(2^0)+1)
Sicne n must be a product of Fermat primes and distinct Fermat numbers
are co-prime, all factors in the decomposition above must be prime.
Since F_5 is composite, we have 1<=s<=5 and
n = F_{s-1} * F_{s-2} * ... * F_0.

Now suppose that n = 9 * \prod_i (2^(2^k_i)+1) where k_i>0.
Then m = 2^t and n=UnitaryPhi(m)=2^t-1 where t=4+\sum_i 2^k_i.
Same arguments suggest that t=2^s. But then n=2^(2^s)-1 is not
divisible by 9 meaning that this case is impossible.

Max