# Decomposition of U(n) based on factorization of n

I am trying to follow an argument about the largest possible order of an element in the multiplicative group of integers $\pmod{n}$, denoted by $U(n)$. I read multiple posts in which people suggested that if $$n = p_1^{k_1}p_2^{k_2} \dots p_n^{k_n}$$ then $$U(n) \cong U(p_1^{k_1})\times U(p_2^{k_2})\times \dots \times U(p_n^{k_n})$$ as a result of the Chinese Remainder Theorem. Could someone help me figuring out how the CRT applies here? Also, would the Funamental Theorem of Finite Abelian Groups help here?

• Apply the CRT to the ring $\mathbb{Z}_n$. Then argue that when you take the units, the decomposition is respected. – Ken Duna Apr 15 '17 at 22:41

Let $[m]_n$ denote the equivalence class of $m$ modulo $n$, so that $U(n) = \{[0]_n,[1]_n, \dots, [n-1]_n\}$.

Note that the map $\phi:U(n) \to U(p_1^{k_1})\times U(p_2^{k_2})\times \dots \times U(p_n^{k_n})$ defined by $$\phi([m]_n) = ([m]_{p_1^{k_1}},[m]_{p_2^{k_2}}, \dots, [m]_{p_r^{k_{r}}})$$ is both well-defined and a homomorphism of groups. The Chinese Remainder theorem is equivalent to the statement that $\phi$ is bijective, which is to say that $\phi$ is an isomorphism. So, the CRT demonstrates that these groups are isomorphic.

The fundamental theorem of finite abelian groups would certainly help here. However, it is a far stronger statement than the one you are trying to make.

• First of all, thank you very much for your answer, it has already helped me out a lot! The way you define $\phi$ makes sense, and I tried to work it out with the example of $n=12$. However, I'm still having difficulties seeing how the CRT is equivalent to saying that $\phi$ is bijective. I know that the CRT says that for any pair of congruences, we are given a unique solution (mod the product of the mods). Is that what ensures that the function is injective? – Nasenhaar Apr 16 '17 at 0:53
• The uniqueness of the solution modulo $n$ tells us that $\phi$ is injective. The fact that such a solution always exists tells us that $\phi$ is surjective. – Omnomnomnom Apr 16 '17 at 1:29