Euler's Totient Function Proving

  • Level: Graduate 
  • Thread starter lil_luc
  • Start date
  • Tags Tags
    Function
1 reply · 3K views · last reply
lil_luc
Messages
5
Reaction score
0
I need some help/hints on how to prove this statement. I don't know where to start!


Prove that if m and n are positive integers such that m|n, then φ(mn) = mφ(n).

Thanks
 
It's a direct consequence of Euler's formula:
[tex] \phi\left(n\right)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_k})[/tex]
Because the hypothesis implies that the prime factorization of m has the same factors as n.

Or you can count the numbers that are coprime with nm in [tex]\left\{1,\ldots,mn\right\}[/tex] and prove that there are as many as the ones that are coprime with n in [tex]\left\{1,\ldots,n\right\}[/tex].