how to calculate $\phi (625)$? Eulers's Totient

Question

euler's totient relies on primes, and coprimes in order to determine $\phi (n)$ but 625 is not the product of any 2 primes, and none of its factors are coprimes so how would you determine $\phi (625)$?

Answer 1

$$\phi(625)=500$$

There are many ways to calculate this. Several are detailed on Wolfram MathWorld; just pick your poison.

Answer 2

From the MathWorld page on Euler's totient function:

If $m = p^{\alpha}$ is a power of a prime, then the numbers that have a common factor with $m$ are the multiples of $p$: $p$, $2p$, ..., $p^{\alpha-1}p$. There are $p^{\alpha-1}$ of these multiples, so the number of factors relatively prime to $p^{\alpha}$ is $$\phi(p^{\alpha}) = p^{\alpha}-p^{\alpha-1} = p^{\alpha-1}(p-1)$$

Let $p = 5$ and $\alpha = 4$ and you get $\phi(625) = 125\cdot 4 = 500$.