Thread: 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 and . i take the function where . By the Chinese Remainder Theorem it seems very clear to me that this function is bijective. Also, this function is well defined since along with the uniqueness of the Chinese Remainder Theorem easily implies that .

however my TA has told me that my function is not injective and encouraged me to instead define my function where 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!

Originally Posted by oblixps

i start by showing that there is a one to one correspondence between and . i take the function where . By the Chinese Remainder Theorem it seems very clear to me that this function is bijective. Also, this function is well defined since along with the uniqueness of the Chinese Remainder Theorem easily implies that .

however my TA has told me that my function is not injective and encouraged me to instead define my function where 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 ? It's not quite clear what exactly the map is?


Anyways, it might be easier to prove that in general any ring isomorphism induces a group isomorphism and so by the CRT one has that and so for which, reading off cardinalities just gives .

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).

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.

yes, and it is not hard to show that it is a ring isomorphism, so then you can follow what drexel28 posted.