# Euler's Totient Function

The totient function, $$\phi(n)$$, is defined as the number of positive integers up to $$n$$ which are relatively prime to $$n$$.

For example, $$\phi(10) = 4$$ because for the interval $$[1,\dots,10]$$, the numbers $$1$$, $$3$$, $$7$$, and $$9$$ are relatively prime to $$10$$.

Therefore, it turns out that if $$n$$ is prime, then $$\phi(n) = n - 1$$.

If $$p$$ is a prime and $$a$$ is a positive integer, then,

$\phi(p^a) = p^a - p^{a-1} \,.$

If $$a$$ and $$b$$ are relatively prime and $$n = ab$$, then $$\phi(n) = \phi(a)\phi(b)$$.