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
if m and n are coprime.
If p is prime and
Euler's product formula states
for each distinct prime number p that divides n.