1
$\begingroup$

Given any number and one of its factors, how can you show that the totient of the factor divides the totient of the original number?

$\endgroup$
  • $\begingroup$ What do you mean $\phi(mn)=\phi(m)+\phi(n)$? $\endgroup$ – Hagen von Eitzen Dec 9 '18 at 0:22
  • $\begingroup$ I know that the totient of a number is equal to the sum of the totient of each of its factors so could we not make that statement since mn can be factored into m and n? $\endgroup$ – Arthur Chong Dec 9 '18 at 0:58
2
$\begingroup$
  • If $p\mid n$ then $\phi(pn)=p\phi(n)$.
  • If $p\nmid n$ then $\phi(pn)=(p-1)\phi(n)$.
$\endgroup$
  • $\begingroup$ How would I exactly use this? I don't have that either m or n are prime. $\endgroup$ – Arthur Chong Dec 9 '18 at 0:59
1
$\begingroup$

Expanding on Hagen's answer: Let $m\mid n$, we need to show that $\phi(m)\mid\phi(n)$. If $m$ is prime then we are done, since $\phi(pm)=p\phi(m)$. If $m$ is not prime, then it can be decomposed into a product of primes, say $\prod p^\alpha$. Then

$$\phi(m)=\phi(\prod p^\alpha)=\prod p^{\alpha-1}\prod(p-1).$$

Now, $\phi(n)$ can be expressed as this product times the totient function of all the extra prime factors $n$ has that is not in $m$. Think of this as because we have "taken out" all the prime powers of $m$ to get that product, and we can do the same thing for $n$ and still have "leftovers". The conclusion follows.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.