Euler totient

Euler's totient function (sometimes called Euler's $\phi$ function) is the function

$\phi(n) =$ # of positive integers $\leq n$ that are relatively prime to $n$.

Properties

Theorem: The function $\phi$ obeys the formula $$\phi(n) = n \displaystyle\prod_{p | n} \left( 1 - \dfrac{1}{p} \right),$$ where the notation $p | n$ indicates that $p$ is a prime that divides $n$.

Proof: proof goes here █