-3
$\begingroup$

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)$?

$\endgroup$
3
  • 3
    $\begingroup$ $625=5^4$, what do you mean it doesn't contain any primes? $\endgroup$
    – Bob Jones
    Nov 12, 2017 at 21:26
  • $\begingroup$ I mean that 625 is not the product of 2 distinct primes. $\endgroup$ Nov 12, 2017 at 21:27
  • 3
    $\begingroup$ Have you done any research? $\endgroup$ Nov 12, 2017 at 21:28

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
0
1
$\begingroup$

$$\phi(625)=500$$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .