# Math Help - Divisibility

1. ## Divisibility

Given that d|n, show that phi(d)|phi(n) if n is a power of a prime. If n=p^k, then phi(n)=p^k-p^(k-1), but I can't make the leap to showing divisibility. Help, please!

2. Originally Posted by tarheelborn
Given that d|n, show that phi(d)|phi(n) if n is a power of a prime. If n=p^k, then phi(n)=p^k-p^(k-1), but I can't make the leap to showing divisibility. Help, please!
If $n=p^k$ then $d\mid n\implies d=p^\ell,\text{ }1\leqslant \ell\leqslant k$. Thus, $\phi(p^\ell)=p^\ell-p^{\ell-1}=p^{\ell-1}\left(p-1\right)$ and $\phi(n)=p^k-p^{k-1}=p^{k-1}(p-1)$. Thus, $\frac{\phi(n)}{\phi(d)}=\frac{p^{k-1}(p-1)}{p^{\ell-1}(p-1)}=p^{k-\ell}\in\mathbb{N}$. It follows that $\phi(d)\mid \phi(n)$