Euler’s Totient Function

In number theory, Euler’s totient function $\varphi (n)$ counts the positive integers up to a given integer $n$ that are coprime with $n$.

There is a very interesting relationship to Fermat’s Little Theorem.

Properties

• If $p$ is a prime number, then $\varphi (p)=p-1$
  • should be pretty obviously since all other numbers all coprime to $p$
• ??? If $p$ is a prime number and $k\ge 1$, then $\varphi (p^k)=p^k-p^{k-1}$
  • Because there are exactly $\frac{p^k}{p}$ numbers that are divisible by $p$
• If $a$ and $b$ are coprime, then $\varphi (ab)=\varphi (a)\cdot \varphi (b)$
  • This relation follow from the Chinese Remainder Theorem $\varphi (ab)=\varphi (a)\cdot \varphi (b)\cdot \frac{d}{\varphi (d)}\text{where }d=\gcd (a,b)$
• Divisor Sum Property (established by Gauss): ${\sum }_{d\mid n}\varphi (d)=n$