Euler Totient Property Proof

[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

 

[DonAntonio]

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.

 

[hawaiifiver]

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

 

[DonAntonio]

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

 

[blue_raver22]

for your question.

The proof you are looking at is using the fact that the Euler totient function, denoted as $$ \phi(n) $$, is a multiplicative function. This means that for relatively prime numbers $$ m $$ and $$ n $$, the totient function of their product is equal to the product of their individual totient functions, as long as the numbers are relatively prime.

In the equation you provided, $$ \prod_{p|mn} \left( 1 - \frac{1}{p} \right) $$ represents the product of all the terms of the form $$ \left( 1 - \frac{1}{p} \right) $$ for all prime numbers $$ p $$ that divide the product $$ mn $$. This product can be rewritten as the product of two separate products, one for the terms that are only factors of $$ m $$ and one for the terms that are only factors of $$ n $$. This gives us the equation:

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

Next, we need to consider the factors that are common to both $$ m $$ and $$ n $$. This is where the greatest common divisor, denoted as $$ (m, n) $$, comes into play. The product of all the terms of the form $$ \left( 1 - \frac{1}{p} \right) $$ for all prime numbers $$ p $$ that divide the greatest common divisor $$ (m, n) $$ can be represented as $$ \prod_{p|(m,n)} \left( 1 - \frac{1}{p} \right) $$.

So, in summary, the equation is showing that the product of all the terms of the form $$ \left( 1 - \frac{1}{p} \right) $$ for all prime numbers $$ p $$ that divide the product $$ mn $$ can be divided into two separate products, one for the terms that are only factors of $$ m $$ and one for the terms that are only factors of $$ n $$. Then, the common factors between $$ m $$ and $$ n $$ are divided out, giving