Results 1 to 5 of 5

Math Help - proving that the euler totient function is multiplicative if (m, n) = 1

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    249

    proving that the euler totient function is multiplicative if (m, n) = 1

    i start by showing that there is a one to one correspondence between  \mathbb{Z}_{mn} and  \mathbb{Z}_m \times \mathbb{Z}_n . i take the function  f:\mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n where  f([x]_{mn}) = ([a]_m, [b]_n) . By the Chinese Remainder Theorem it seems very clear to me that this function is bijective. Also, this function is well defined since  [x]_{mn} = [y]_{mn} along with the uniqueness of the Chinese Remainder Theorem easily implies that  f([x]_{mn}) = f([y]_{mn}) .

    however my TA has told me that my function is not injective and encouraged me to instead define my function  f:\mathbb{Z}_m \times \mathbb{Z}_n \rightarrow \mathbb{Z}_{mn} where  f([a]_m, [b]_n) = [x]_{mn} but this way of defining it seems to me more difficult to show is bijective than the other.

    Next i show that an element is a unit in one set if and only if it is a unit in the other set. This comes from the fact that (x, mn) = 1 if and only if (x, m) = 1 and (x, n) = 1 which is easy to prove. Therefore the number of units in both sets are the same and since the cardinality of the set is the value of the euler function the result follows.

    i know i'm missing small details but are the contents of my proof correct? would it be beneficial to add or subtract anything in it? and as for defining a function that is bijective between the sets, was my TA right in cautioning me against defining my function in that way? thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: proving that the euler totient function is multiplicative if (m, n) = 1

    Quote Originally Posted by oblixps View Post
    i start by showing that there is a one to one correspondence between  \mathbb{Z}_{mn} and  \mathbb{Z}_m \times \mathbb{Z}_n . i take the function  f:\mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n where  f([x]_{mn}) = ([a]_m, [b]_n) . By the Chinese Remainder Theorem it seems very clear to me that this function is bijective. Also, this function is well defined since  [x]_{mn} = [y]_{mn} along with the uniqueness of the Chinese Remainder Theorem easily implies that  f([x]_{mn}) = f([y]_{mn}) .

    however my TA has told me that my function is not injective and encouraged me to instead define my function  f:\mathbb{Z}_m \times \mathbb{Z}_n \rightarrow \mathbb{Z}_{mn} where  f([a]_m, [b]_n) = [x]_{mn} but this way of defining it seems to me more difficult to show is bijective than the other.

    Next i show that an element is a unit in one set if and only if it is a unit in the other set. This comes from the fact that (x, mn) = 1 if and only if (x, m) = 1 and (x, n) = 1 which is easy to prove. Therefore the number of units in both sets are the same and since the cardinality of the set is the value of the euler function the result follows.

    i know i'm missing small details but are the contents of my proof correct? would it be beneficial to add or subtract anything in it? and as for defining a function that is bijective between the sets, was my TA right in cautioning me against defining my function in that way? thanks!
    What precisely do you mean by x\mapsto (a,b)? It's not quite clear what exactly the map is?


    Anyways, it might be easier to prove that in general any ring isomorphism R\to S induces a group isomorphism U(R)\to U(S) and so by the CRT one has that \mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n and so U(\mathbb{Z}_{nm})\cong U(\mathbb{Z}_n\times\mathbb{Z}_m)= U(\mathbb{Z}_n)\times U(\mathbb{Z}_m) for which, reading off cardinalities just gives \varphi(nm)=\varphi(n)\varphi(m).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,273
    Thanks
    666

    Re: proving that the euler totient function is multiplicative if (m, n) = 1

    the problem with your proof, is given x, how do you produce a and b? even if you know that [x]_mn = [ab]_mn, a and b may not be unique. for example, let m = 10, n = 12.

    then does f(6) = (3,2), or (1,6)?

    you could define f([x]_mn) = ([x]_m, [x]_n), (which may be what you were thinking), but this is only injective when gcd(m,n) = 1 (which is the case, here).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2008
    Posts
    249

    Re: proving that the euler totient function is multiplicative if (m, n) = 1

    oh oops! yes sorry i did mean f([x]_mn) = ([x]_m, [x]_n). would this definition of the function make sense? i was thinking that for every a and b, represented as ([a]_m, [b]_n), the CRT guarantees me a unique [x]_mn such that [x]_m = [a]_m and [x]_n = [b]_n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,273
    Thanks
    666

    Re: proving that the euler totient function is multiplicative if (m, n) = 1

    yes, and it is not hard to show that it is a ring isomorphism, so then you can follow what drexel28 posted.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 5th 2010, 01:04 AM
  2. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 09:41 AM
  3. Reload this Page Euler's Totient Function Proving
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 1st 2010, 07:03 PM
  4. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 06:11 PM
  5. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2009, 07:16 PM

Search Tags


/mathhelpforum @mathhelpforum