2
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Nasenhaar Apr 16 '17 at 0:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Omnomnomnom Apr 16 '17 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.