# Euler’s Totient Function

In number theory, Euler’s totient function $ϕ(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 $ϕ(p)=p−1$
- should be pretty obviously since all other numbers all coprime to $p$

- ??? If $p$ is a prime number and $k≥1$, then $ϕ(p_{k})=p_{k}−p_{k−1}$
- Because there are exactly $pp_{k} $ numbers that are divisible by $p$

- If $a$ and $b$ are coprime, then $ϕ(ab)=ϕ(a)⋅ϕ(b)$
- This relation follow from the Chinese Remainder Theorem $ϕ(ab)=ϕ(a)⋅ϕ(b)⋅ϕ(d)d whered=g(a,b)$

- Divisor Sum Property (established by Gauss): $∑_{d∣n}ϕ(d)=n$