# How to show $\varphi (ab) = d\varphi(a)\varphi(b) / \varphi(d)$? [duplicate]

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

-

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

This question was marked as an exact duplicate of an existing 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 en.wikipedia.org/wiki/Euler's_totient_function – Beni Bogosel Apr 16 '12 at 12:51

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)$.