Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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