Results 1 to 6 of 6

Math Help - Proof about Euler's φ-function

  1. #1
    Junior Member
    Joined
    Apr 2010
    Posts
    58

    Proof about Euler's φ-function

    Prove that if m,n are positive integers with (m,n)=1, then φ(m.n) = φ(m)φ(n).

    I was told to use the Chinese Remainder Theorem to show that wach pair of elements [a]n & [a]m (in Zm, Zn respectively) corresponds to a unique element [x]mn in Zmn. Then show that this correspondence, [a] & [b] are units if and only if [x] is a unit.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    In general is...

    \displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p}) (1)

    ... so that if m and n have no common prime factors is...

    \displaystyle \varphi(m\ n)= m\ \prod_{p|m} (1-\frac{1}{p})\ n\ \prod_{p|n} (1-\frac{1}{p})= \varphi(m)\ \varphi(n) (2)

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by page929 View Post
    Prove that if m,n are positive integers with (m,n)=1, then φ(m.n) = φ(m)φ(n).

    I was told to use the Chinese Remainder Theorem to show that wach pair of elements [a]n & [a]m (in Zm, Zn respectively) corresponds to a unique element [x]mn in Zmn. Then show that this correspondence, [a] & [b] are units if and only if [x] is a unit.
    I assume your [a]m was supposed to be [b]m? I think the hint is almost a proof in itself! Where are you stuck?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by chisigma View Post
    In general is...

    \displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p}) (1)



    I don't think they can use this...in fact, as far as I remember, to reach this formula one must first know the multiplicativity of \phi and its values on powers of primes.
    If they ould use this formula the question would be utterly trivial

    Tonio


    ... so that if m and n have no common prime factors is...

    \displaystyle \varphi(m\ n)= m\ \prod_{p|m} (1-\frac{1}{p})\ n\ \prod_{p|n} (1-\frac{1}{p})= \varphi(m)\ \varphi(n) (2)

    Kind regards

    \chi \sigma
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    In ...

    Totient Function -- from Wolfram MathWorld

    ... is written the following precedure...

    ... the 'fundamental theorem of arythmetic' extablishes that any integer m>1 is represented as the product...

    \displaystyle m= \prod_{k=1}^{r} p_{k}^{\alpha_{k}} (1)

    ... where p_{k} , k=1,2,...,r are the r distincts primes deviding m. If m= p^{\alpha} the numbers of factors relatively prime to m is...

    \displaystyle \varphi (m) = p^{\alpha}\ (1-\frac{1}{p}) (2)

    If m= p_{1}^{\alpha_{1}}\ p_{2}^{\alpha_{2}} the numbers of factors relative prime to m is...

    \displaystyle \varphi (m) = p_{1}^{\alpha_{1}}\ (1-\frac{1}{p_{1}})\ p_{2}^{\alpha_{2}}\ (1-\frac{1}{p_{2}}) = m\  (1-\frac{1}{p_{1}})\ (1-\frac{1}{p_{2}}) (3)

    Proceeding by induction we arrive at the formula...

    \displaystyle \varphi(m)= m\ \prod_{k=1}^{r} (1-\frac{1}{p_{k}}) (4)

    It is remarkable the fact that the (4) has beeen derived only from (1) [i.e. the fundamental theorem of arithmetic...] without any other hypothesis, so that the formula valid for m and n coprimes...

    \varphi(m\ n) = \varphi (m)\ \varphi (n) (5)

    ... is derived from (4) and not viceversa...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by chisigma View Post
    In ...

    Totient Function -- from Wolfram MathWorld

    ... is written the following precedure...

    ... the 'fundamental theorem of arythmetic' extablishes that any integer m>1 is represented as the product...

    \displaystyle m= \prod_{k=1}^{r} p_{k}^{\alpha_{k}} (1)

    ... where p_{k} , k=1,2,...,r are the r distincts primes deviding m. If m= p^{\alpha} the numbers of factors relatively prime to m is...

    \displaystyle \varphi (m) = p^{\alpha}\ (1-\frac{1}{p}) (2)

    If m= p_{1}^{\alpha_{1}}\ p_{2}^{\alpha_{2}} the numbers of factors relative prime to m is...

    \displaystyle \varphi (m) = p_{1}^{\alpha_{1}}\ (1-\frac{1}{p_{1}})\ p_{2}^{\alpha_{2}}\ (1-\frac{1}{p_{2}}) = m\  (1-\frac{1}{p_{1}})\ (1-\frac{1}{p_{2}}) (3)

    Proceeding by induction we arrive at the formula...

    \displaystyle \varphi(m)= m\ \prod_{k=1}^{r} (1-\frac{1}{p_{k}}) (4)

    It is remarkable the fact that the (4) has beeen derived only from (1) [i.e. the fundamental theorem of arithmetic...] without any other hypothesis


    This is interesting and I wasn't aware of it, but it isn't completely accurate: only in point (13) arrives Wolfram to the formula, after having used induction and, in (6)-(7)-(8) using a not so straightforward deduction on different primes dividing a given natural number n.

    Anyway, is another way to approach this.

    Tonio


    , so that the formula valid for m and n coprimes...

    \varphi(m\ n) = \varphi (m)\ \varphi (n) (5)

    ... is derived from (4) and not viceversa...

    Kind regards

    \chi \sigma
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euler function proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 23rd 2011, 08:44 AM
  2. Euler Function Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 5th 2011, 12:04 AM
  3. [SOLVED] Can someone help with a proof involving Euler's phi function?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 27th 2010, 09:25 PM
  4. Euler's phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 7th 2010, 08:46 PM
  5. Euler phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 29th 2009, 09:58 PM

Search Tags


/mathhelpforum @mathhelpforum