proof that all powers of 3 are perfect totient numbers


Given an integer x>0, it is always the case that

3x=i=1c+1ϕi(3x),

where ϕi(x) is the iterated totient function and c is the integer such that ϕc(n)=2. That is, all integer powers of three are perfect totient numbers.

The proof of this is easy and even considered trivial. Here it goes anyway:

Accepting as proven that ϕ(px)=(p-1)px-1, we can plug in p=3 and see that ϕ(3x)=2(3x-1), which falls short of 3x by 3x-1. Given the proof that Euler ϕ is a multiplicative functionMathworldPlanetmath (http://planetmath.org/ProofThatEulerPhiIsAMultiplicativeFunction) and the fact that ϕ(2)=1, it is obvious that ϕ(2(3x-1))=ϕ(3x-1). Therefore, each iterate will be twice a power of three, with the exponentMathworldPlanetmath gradually decreasing as the iterator nears c. To put it algebraically, ϕi(3x)=2(3c-i) for ic. Adding up in ascending order starting at the (c+1)th iterate, we obtain 1+2+6+18++2(3x-2)+2(3x-1)=3x.

References

  • 1 D. E. Ianucci, D. Moujie & G. L. Cohen, “On Perfect Totient Numbers” Journal of Integer Sequences, 6, 2003: 03.4.5
Title proof that all powers of 3 are perfect totient numbers
Canonical name ProofThatAllPowersOf3ArePerfectTotientNumbers
Date of creation 2013-03-22 16:34:32
Last modified on 2013-03-22 16:34:32
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 11
Author PrimeFan (13766)
Entry type Proof
Classification msc 11A25