How to calculate Euler Totients Function for a large number?

Question

I heard the main tool is multiplicativity: $ϕ(ab)=ϕ(a)ϕ(b)$ if $\gcd(a,b)=1$.

However I am struggling to find two numbers that would work for $ϕ(375)$?

Also I cannot use this method: $ϕ(p^k)=p^k−p^{k−1}$ because no prime numbers exist that can form $375$ using $p^k$.

Thanks

Answer 1

What you want is the Euler product formula

$$ \phi(n) = n \prod\limits_{p|n} 1 - p^{-1} = n \prod\limits_{p|n} \frac{p-1}{p}$$

Simply factorize $n$ into primes, and use this formula to compute the totient.

For example, $375 = 3\cdot 5^3$, so

$$\phi(375) = 375\cdot\frac{2}{3}\cdot\frac{4}{5} = 200$$

Note that the product is taken over distinct primes $p$, so the fact that $5$ is a factor with multiplicity $3$ is not important in this calculation (in fact it is taken into account by the factor of $n$ in the front).