Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Proof of a formula involving Euler's totient function.

For positive integers $m$ and $n$ where $d=gcd(m,n)$, show that $$\phi(mn) = \phi(m)\phi(n)\frac{d}{\phi(d)}$$

This is just the generalization of the multiplicative property of phi function.I have tried to solve this in the same way as the proof of multiplicative property but couldn't get far.Please help.

share|improve this question

marked as duplicate by Martin Sleziak, lhf, t.b., Zev Chonoles Jun 17 '12 at 21:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
You can find som proofs in this question (and in the questions linked to it): Proof of a formula involving Euler's totient function. –  Martin Sleziak Jun 17 '12 at 10:08
1  
See also math.stackexchange.com/questions/119911/… –  lhf Jun 17 '12 at 12:06
add comment

1 Answer 1

Suppose $$d=q_1^{\gamma_1}\cdot\ldots\cdot q_k^{\gamma_k}\,,\,m=d\cdot p_1^{\alpha_1}\cdot\ldots\cdot p_r^{\alpha_r}\,,\,n=d\cdot t_1^{\beta_1}\cdot\ldots\cdot t_s^{\beta_s}$$with $\,p_i\,,\,q_i\,,\,t_i\,$ primes , $\,\alpha_i\,,\,\beta_i\,,\,\gamma_i\in\mathbb{N}\,$ . Then, we have$$\varphi(mn)=mn\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)\prod_{j=1}^s\left(1-\frac{1}{t_j}\right)\prod_{l=1}^k\left(1-\frac{1}{q_l}\right)$$$$\varphi(m)=m\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)\,,\,\varphi(n)=n\prod_{j=1}^s\left(1-\frac{1}{t_j}\right)$$$$\varphi(d)=d\prod_{l=1}^k\left(1-\frac{1}{q_l}\right)$$The wanted equality follows at once.

share|improve this answer
    
Shouldn't this is correct $$\varphi(m)=m\prod_{i=1}^r\left(1-\frac{1}{p_i}\right) \prod_{l=1}^k\left(1-\frac{1}{q_l}\right)$$ same for $\varphi(n)$ –  Saurabh Jun 17 '12 at 10:40
    
Of course, @Saurabh. Thank you, I'll edit it. –  DonAntonio Jun 17 '12 at 10:45
add comment

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