# proof that all powers of 3 are perfect totient numbers

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

 $3^{x}=\sum_{i=1}^{c+1}\phi^{i}(3^{x}),$

where $\phi^{i}(x)$ is the iterated totient function and $c$ is the integer such that $\phi^{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 $\phi(p^{x})=(p-1)p^{x-1}$, we can plug in $p=3$ and see that $\phi(3^{x})=2(3^{x-1})$, which falls short of $3^{x}$ by $3^{x-1}$. Given the proof that Euler $\phi$ is a multiplicative function (http://planetmath.org/ProofThatEulerPhiIsAMultiplicativeFunction) and the fact that $\phi(2)=1$, it is obvious that $\phi(2(3^{x-1}))=\phi(3^{x-1})$. Therefore, each iterate will be twice a power of three, with the exponent gradually decreasing as the iterator nears $c$. To put it algebraically, $\phi^{i}(3^{x})=2(3^{c-i})$ for $i\leq c$. Adding up in ascending order starting at the $(c+1)$th iterate, we obtain $1+2+6+18+\cdots+2(3^{x-2})+2(3^{x-1})=3^{x}$.

## 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 ProofThatAllPowersOf3ArePerfectTotientNumbers 2013-03-22 16:34:32 2013-03-22 16:34:32 PrimeFan (13766) PrimeFan (13766) 11 PrimeFan (13766) Proof msc 11A25