# Relation Between $(\mathbb{Z}/a\mathbb{Z})^\times$ and $(\mathbb{Z}/ab\mathbb{Z})^\times$

How can we prove that if there exists an element of order $c$ in $(\mathbb{Z}/a\mathbb{Z})^\times$ then there must exist some element of order $c$ in $(\mathbb{Z}/ab\mathbb{Z})^\times$?

-
Do you mind telling what $U_x$ stands for? – Mercy King Jul 3 '12 at 14:29
Not everybody reads th same book and at the same time: what do you mean by$\,U_a\,$? Is it the group of units in some ring, is it the cyclic group of order a...what? – DonAntonio Jul 3 '12 at 14:30
Assuming $U_m$ is the group of units of $\mathbb Z/(m)$, are $a$ and $b$ relatively prime? – lhf Jul 3 '12 at 14:33
If $(a,b)=1$ and $x\in U_a$ has order $c$, then $y\equiv x\bmod a$ and $y\equiv 1\bmod b$ should be simultaneously solvable by CRT, and $y\in U_{ab}$ with $y^c\equiv 1$ (again by CRT). – anon Jul 3 '12 at 14:42
@TimothySalus, please edit your question and add that information. It might be useful to mention which book is that. – lhf Jul 3 '12 at 23:43

This follows easily from the fact that $(\mathbb Z/p^m\mathbb Z)^\times$ is (isomorphic to) a subgroup of $(\mathbb Z/p^n\mathbb Z)^\times$ whenever $m \le n$. A brief sketch of this claim follows.
For $p$ odd, both groups are cyclic and the order of one divides the other. For $p=2$, the group $(\mathbb Z/2^m\mathbb Z)^\times$ is isomorphic to $\mathbb Z/2 \times \mathbb Z/2^{m-2}\mathbb Z$ provided $m \ge 2$, so again the claim holds for $2 \le m \le n$. When $p=2$ and $m=1$ the claim is trivial.
It seems like you're comfortable with the reductions needed to apply Erick's answer. A sketch for the curious reader: (1) Chinese remainder theorem (2) $(A \times B)^* = A^* \times B^*$ (3) If $x$ and $y$ are elements of a group which commute, then the order of $xy$ is the l.c.m. of the orders of $x$ and $y$.
Here's a slightly different argument for the last step. If $n \geq m$ are natural numbers then the reduction map $\mathbb Z/p^n\mathbb Z \to \mathbb Z/p^m\mathbb Z$ induces a surjective map on unit groups $(\mathbb Z/p^n\mathbb Z)^* \to (\mathbb Z/p^m\mathbb Z)^*$. [Why?] If you have an element of order $k$ in $(\mathbb Z/p^m\mathbb Z)^*$ then its preimages under this map have orders divisible by $k$.