Sign up ×
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.

I have this interesting question that I have difficulty to prove.

I know that:

$ \gcd(a,b) = d $

And I need tho show that:

$ \varphi(ab) = d\varphi(a)\varphi(b) / \varphi(d) $

where $\varphi$ is Euler's totient function

share|cite|improve this question

marked as duplicate by lhf, Benjamin Lim, Bill Dubuque, Martin Sleziak, t.b. Apr 16 '12 at 17:16

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.

There is an explicit formula for $\varphi(n)$ in terms of the prime divisors of $n$. Using that should be pretty straight forward here. See's_totient_function – Beni Bogosel Apr 16 '12 at 12:51

1 Answer 1

For any prime p, let m1 be greatest power of p that divides a and n1 be greatest power of p that divides b. Let m be max of m1 and n1 and n be min of m1 and n1. p's contribution to $φ(ab)$ is $p^{m+n}(1-1/p)$ Contribution to $dφ(a)φ(b) / φ(d)$ is $p^n . p^{m1}(1-1/p) . p^{n1}(1-1/p) / (p^{n}(1-1/p))$, which equals $p^{m1}.p^{n1}(1-1/p) = p^{m1+n1}(1-1/p) = p^{m+n}(1-1/p)$.

share|cite|improve this answer

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