UPhi

[koh]

    Max wrote : 

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

    Thank you for the nice proof using one of the most recent theorem in number theory.

    Yasutoshi