1
$\begingroup$

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

  • 1
    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 http://en.wikipedia.org/wiki/Euler's_totient_function2012-04-16

1 Answers 1

0

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