Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler Totient Property Proof

  1. Jun 28, 2012 #1

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

  2. jcsd
  3. Jun 28, 2012 #2
    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.
  4. Jun 28, 2012 #3
    Hi DonAntonio,

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

  5. Jun 28, 2012 #4

    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 [itex]\,p_k,q_i\,[/itex] prime numbers, [itex]\,a_k,b_i\in \mathbb N[/itex] . 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 [itex] \,d_j=min\{a_j,b_j\}[/itex] , 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.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Euler Totient Property Proof
  1. Euler totient puzzle (Replies: 2)