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)\).