Results 1 to 4 of 4

Math Help - is phi multiplicative

  1. #1
    Junior Member
    Joined
    Oct 2006
    Posts
    33

    is phi multiplicative

    can somoene pls prrovide a complete proof that if (m1,m2) =1 then phi(m) is multiplicative?

    and can someone pls provide me a method for computing phi(2004)

    Thanks in advance
    Edgar
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    1. Given that \sum_{d|n}\phi(d)=n by Möbius inversion formula we have that n\cdot{\sum_{d|n}\frac{\mu(d)}{d}}=\phi(n) and since \frac{\mu(n)}{n}is multiplicative it follows that n\cdot{\sum_{d|n}\frac{\mu(d)}{d}}=\phi(n) is multiplicative (if f(n) is multiplicative then so is \sum_{d|n}f(d))

    Note also that \sum_{d|n}\frac{\mu(d)}{d}=\prod_{p|n}\left(1-\frac{1}{p}\right) (where the product runs through the prime divisors of n)

    Thus: n\cdot{\prod_{p|n}\left(1-\frac{1}{p}\right)}=\phi(n)

    2. Consider the Inclusion-exclusion principle - Wikipedia, the free encyclopedia
    and calculate n-\phi(n), and from there find the formula for \phi(n) and conclude that it's multiplicative

    To calculate \phi(2004) find the prime divisors of 2004, these are 2,3 and 167 thus: 2004\cdot{\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{167}\right)}=\phi(2004)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2006
    Posts
    33

    is phi multiplicative

    thanks for your response.

    with regards caluclating phi(2004)

    2004 = 2 x 2 x 3 x 167

    is it a rule that you do not repeat the primes being used when usin the formula ie only use two once in the formula even though it appears twice?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Here is another proof.
    Let a be a positive integer. Define X_a = \{ 1\leq x\leq a | \gcd( a,x)=1\}.

    We will prove that |X_{nm}| = |X_n||X_m| if \gcd(n,m)=1.
    Define \phi: X_{nm} \mapsto X_n\times X_m as (x\bmod n,x\bmod m). Where \bmod n,\bmod m is reduction modolu n and m.
    Now use the Chinese Remainder Theorem to prove this is one-to-one and onto.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Multiplicative inverse 71.7
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 26th 2009, 10:34 AM
  2. GCD Multiplicative Property
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 8th 2009, 09:50 PM
  3. multiplicative
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2008, 07:22 PM
  4. Multiplicative Set
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 29th 2008, 03:36 PM
  5. Multiplicative inverse
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 14th 2006, 02:53 PM

Search Tags


/mathhelpforum @mathhelpforum