1
$\begingroup$

I know how to compute $\phi(x)$ like $\phi(21)$ or $\phi(7)$ but how can I compute $\phi(x^y)$. Specifically how can I compute $\phi(5^{20})$?

$\endgroup$
0

3 Answers 3

2
$\begingroup$

You can use the general formula: if |$d =gcd(m,n)$ then

$$\phi(mn)=\phi(m) \phi(n)\frac{d}{\phi( d)}$$

In particular, if $m|n$ then $d=m$ an you get

$$\phi(mn)=m\phi(n) \,.$$

Then, by induction of $y$ you can prove that

$$\phi(x^y)=x^{y-1} \phi(x)$$

$\endgroup$
0
$\begingroup$

You may use the well known equality

$$\Bbb N\ni n=p_1^{a_1}\cdot\ldots\cdot p_k^{a_k}\;,\;\;p_i\;\;\text{primes}\;,\;\;a_i\in\Bbb N\implies$$

$$\implies \varphi(n)=n\prod_{m=1}^k\left(1-\frac1{p_m}\right)$$

So for your question: only put $\;x^y\;$ in place of $\;n\;$ above, as the prime factors are the same...

$\endgroup$
0
$\begingroup$

It is easy to calculate $\phi(p^k)$ if $p$ is prime.

Using the definition $\phi(p^k)$ is the number of numbers $1\leq i\leq p^k$ such that hcf$(i,p^k)=1$. Well, in this range, only the numbers $p,2p,3p,...,(p^{k-1})p$ share a prime factor with $p^k$. There are $p^{k-1}$ of these.

So $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$.

$\endgroup$

You must log in to answer this question.

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