# Finding an explicit isomorphism between $\mathbb{Z}^{\times}_n$ and $\mathbb{Z}^{\times}_{2n}$

For an odd integer $n$, find an explicit isomorphism between $\mathbb{Z}^{\times}_n$ and $\mathbb{Z}^{\times}_{2n}$.
How do I do this? I don't really know where to start. I can easily find bijections but am yet to find a structure preserving one.

-
are you familiar with the Chinese Remainder Theorem? – Qiaochu Yuan May 19 '11 at 15:08
@Qiaochu: How can u find a bijection when their orders is different. – user9413 May 19 '11 at 15:32
@Chandru: Their orders are not different. $\# (\mathbb{Z}/n \mathbb{Z})^{\times} = \phi(n)$ and $\phi(n)=\phi(2n)$ if $2 \nmid n$. – Brandon Carter May 19 '11 at 15:59
@Brandon: Yeah this is what I wanted to know. – user9413 May 19 '11 at 16:05

If $R$ is any ring, let $R^{\times}$ be its group of units. Then if

$f: R \rightarrow S$

is a ring homomorphism, it restricts to a group homomorphism

$f^{\times}: R^{\times} \rightarrow S^{\times}$

on the unit groups. Here you have a natural (i.e., quotient) map

$f: \mathbb{Z}/2n \mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}$

so $f^{\times}$ is a homomorphism between two finite groups that you want to show are isomorphic. Since they are finite and you say you already know that they have the same order, you are in a good place: it suffices to show either that $f^{\times}$ is injective or that $f^{\times}$ is surjective. Give it a try.

(But, to be sure, if $f^{\times}$ is in fact an isomorphism, you can presumably show that it is both injective and surjective from scratch, so you don't actually need to know that $\varphi(2n) = \varphi(n)$ for odd $n$ in advance -- not that this is at all hard to see.)

By the way, studying the injectivity/surjectivity of $f_{m,n}^{\times}$ where

$f_{m,n}: \mathbb{Z}/mn \mathbb{Z} \rightarrow \mathbb{Z}/n \mathbb{Z}$

is a good exercise in general -- i.e., for any $m,n \in \mathbb{Z}^+$. It's a nice mixture of algebra and number theory.

-
Since they are finite and you say you already know that they have the same order: I don't understand this statement. Do $\mathbb{Z}_{n}^{\times}$ and $\mathbb{Z}_{2n}^{\times}$ both as groups have same order? – user9413 May 20 '11 at 11:24
@Chandru: yes. The OP says she knows that already, but it also follows from filling in the details of the argument I've sketched. (Wasn't this already asked and answered in the comments above?) – Pete L. Clark May 20 '11 at 11:38

HINT $\:$ It's very easy. The natural quotient map $\rm\ a+2\:n\ \mathbb Z\ \mapsto\ a+n\ \mathbb Z\$ is surjective (so injective) on units, $\:$ since $\rm\:n\:$ odd $\:\Rightarrow\:$ one of $\rm\:a,\ a+n\:$ is odd, $\:$ so is coprime to $\rm\:2\:n\iff$ coprime to $\rm\:n\:.$

-

The following solution is concrete in the extreme. Look at the particular example $n=15$. Then the elements of $\mathbb{Z}^\times_n$ can be thought of as the numbers $1$, $2$, $4$, $7$, $8$, $11$, $13$, and $14$, under multiplication modulo $15$. Similarly, the elements of
$\mathbb{Z}^\times_{2n}$ can be thought of as the numbers $1$, $7$, $11$, $13$, $17$, $19$, $23$, $29$ under multiplication modulo $30$. Note that these numbers are all odd.

What should our attempted isomorphism $\phi$ do to the elements of $\mathbb{Z}^\times_n$? The idea is to send $k$ to something that is as "like" $k$ as possible. Obviously $\phi$ should send $1$ to $1$. What should $\phi(2)$ be? The only element of $\mathbb{Z}^\times_{2n}$ that is congruent to $2$ modulo $n$ is $2+15$, so it is reasonable to send $2$ to $17$.

In general, suppose that $1 \le k \le 14$, and $k$ is relatively prime to $15$. Then if $k$ is odd, we let $\phi(k)=k$. And if $k$ is even, we let $\phi(k)=k+15$.

It is easy to see that $\phi$ is a bijection. It remains to show that $\phi(ij)=\phi(i)\phi(j)$. This divides naturally into $3$ cases: (i) $i$, $j$ both odd; (ii) $i$, $j$ both even; and (iii) one is odd and the other is even.

Out of impatience, we do them all together. Note that by the definition of $\phi$, we have $\phi(ij) \equiv \phi(i)\phi(j) \pmod{n}$. But also, again from the definition, $\phi(ij) \equiv \phi(i)\phi(j) \pmod{2}$, since on each side we have an odd number. It follows that $\phi(ij) \equiv \phi(i)\phi(j)\pmod{2n}$, which is exactly what we want.

The idea generalizes immediately to any odd $n$. I do not know what notation you use for the elements of $\mathbb{Z}^\times_n$. I will assume that you use the notation $i/(n)$ for the equivalence class of $i$.

Look at the equivalence class $i/(n)$, where $1 \le i \le n-1$. If $i$ is odd, let $\phi(i/(n))=i/(2n)$. If $i$ is even, let $i'=i+n$, and let $\phi(i/(n))=i'/(2n)$. It is straightforward to show that $\phi$ is an isomorphism from $\mathbb{Z}^\times_n$ to $\mathbb{Z}^\times_{2n}$.

Now that you have a concrete picture of what is happening, you can begin to understand more abstract solutions, and appreciate their elegance.

-