## Euler Totient Property Proof

Hello,

I am looking at the proof (Theorem 2.5 (b) Apostol) of $$\phi (mn) = \phi(m) \phi(n) \frac{d}{\phi(d)}$$ where $$d = (m, n)$$.

Can someone explain how they go from

$$\prod_{p|mn} \left( 1 - \frac{1}{p} \right) = \frac{\prod_{p|m} \left( 1 - \frac{1}{p} \right) \prod_{p|n} \left( 1 - \frac{1}{p} \right) }{\prod_{p| (m, n)} \left( 1 - \frac{1}{p} \right)}$$

Thanks

 PhysOrg.com science news on PhysOrg.com >> Heat-related deaths in Manhattan projected to rise>> Dire outlook despite global warming 'pause': study>> Sea level influenced tropical climate during the last ice age

 Quote by hawaiifiver Hello, I am looking at the proof (Theorem 2.5 (b) Apostol) of $$\phi (mn) = \phi(m) \phi(n) \frac{d}{\phi(d)}$$ where $$d = (m, n)$$. Can someone explain how they go from $$\prod_{p|mn} \left( 1 - \frac{1}{p} \right) = \frac{\prod_{p|m} \left( 1 - \frac{1}{p} \right) \prod_{p|n} \left( 1 - \frac{1}{p} \right) }{\prod_{p| (m, n)} \left( 1 - \frac{1}{p} \right)}$$ Thanks
You can split the divisors of a product of two numbers in divisors of first number, divisors of the second one and divisors of both. These last ones

are, of course, precisely the divisors of the g.c.d. of both numbers. This is is the reason of your formula.

 Quote by DonAntonio You can split the divisors of a product of two numbers in divisors of first number, divisors of the second one and divisors of both. These last ones are, of course, precisely the divisors of the g.c.d. of both numbers. This is is the reason of your formula.
Hi DonAntonio,

Thanks for the swift reply. Forgive my ignorance, but is there need for a proof of that "method"

Thanks

## Euler Totient Property Proof

 Quote by hawaiifiver Hi DonAntonio, Thanks for the swift reply. Forgive my ignorance, but is there need for a proof of that "method" Thanks

Well, of course. It is annoying though pretty elementary. Suppose $$m=\prod_{k=1}^r p_k^{a_k}\,\,,\,\,n=\prod_{i=1}^s q_i^{b_i}$$with $\,p_k,q_i\,$ prime numbers, $\,a_k,b_i\in \mathbb N$ . Suppose there is a natural number

$$\,z\leq k,i\,\,\,s.t.\,\,\,p_1=q_1,\ldots ,p_z=q_z\Longrightarrow d=g.c.d(m,n)=\prod_{j=1}^z p_z^{d_j}$$with $\,d_j=min\{a_j,b_j\}$ , or in words: the maximal common divisor of two

numbers is the product of the common primes to both numbera, each prime raised to the minimal power appearing in

either of both numbers

We thus can write now
$$m=d\prod_{k=z+1}^rp_k^{a_k}\,\,,\,\,q=d\prod_{i=z+1}^s q_i^{b_i}\Longrightarrow \varphi(mn)=mn\prod_{j=1}^z\left(1-\frac{1}{p_j}\right)\prod_{k=z+1}^r\left(1-\frac{1}{p_k}\right)\prod_{i=z+1}^s\left(1-\frac{1}{q_i}\right)$$and since
$$\prod_{j=1}^z\left(1-\frac{1}{p_j}\right)=\frac{\varphi(d)}{d}$$the formula you want follows at once.

DonAntonio