Totient Function
Notes
Euler's totient or phi function of an integer n,
)
, counts the positive integers less than or equal to n that are relatively prime to n. The totient function is multiplicative, that is
=\phi(m) \phi(n))
if m and n are coprime.
If p is prime and
then
=p^k \left( 1 - \frac{1}{p}\right))
Euler's product formula states
=n \Pi_{p|n} \left( 1- \frac{1}{p}\right))
for each distinct prime number p that divides n.
