Prove that if a, b are relatively prime integers, then $\Bbb{Z}/ab\Bbb{Z}$ is isomorphic to $\mathbb{Z}/a\Bbb{Z} \times \Bbb{Z}/b\Bbb{Z}$.

Question

I know this is related to the Chinese remainder theorem but I'm having trouble showing there is an isomorphism between the mapping $\mathbb{Z}/ab\mathbb{Z}$ to $\mathbb{Z}/a\mathbb{Z} \times \mathbb{Z}/b\mathbb{Z}$.

Thank You.

Answer 1

Define the map $f:\Bbb Z/ab\Bbb Z\to \Bbb Z/a\Bbb Z*\Bbb Z/b\Bbb Z$ as follows: $$f(x\pmod{ ab}):=(x\pmod a, x\pmod b)$$

Observe that $\Bbb Z/ab\Bbb Z$ , and $\Bbb Z/a\Bbb Z*\Bbb Z/b\Bbb Z$ both have $ab$ elements. So, it suffices to prove that $f$ is one-to-one, hence it will be onto. So, if

$$\small{(x\pmod a,x\pmod b) = (y\pmod a,y\pmod b)},$$

$ a\mid x - y$, and $b\mid x - y$. Since $(a,b) = 1$, $ab\mid x - y$. This means $x\equiv y\pmod{ab}$. So, $f$ is one to one.

Answer 2

The isomorphism is $\phi(ab+N\mathbb{Z})=(a+N\mathbb{Z},b+N\mathbb{Z})$

First show it is a homomorphism, then show it is injective and surjective - this proof is an application of the Chinese Remainder Theorem.

We note that an isomorphism is a bijective homomorphism, so we need to show (1) that $\phi$ is a homomorphism and (2) that $\phi$ is bijective.

(1) $\phi$ is trivially a homomorphism because $\mathbb{Z/nZ} \times \mathbb{Z/mZ}$ is a group, and $\phi(a+b)=\phi(a)+\phi(b) \forall a,b \in \mathbb{Z/mnZ}$

(2) a. $\phi$ is injective because $\phi(a) = \phi(b)$ if and only if $a=b$. An ordered pair is only equal if their components are equal.

b. $\phi$ is surjective if and only if $\forall a+\mathbb{Z/n},b+\mathbb{Z/mZ}$, $\exists c$ such that $\phi(c+\mathbb{Z/nmZ})=(a+\mathbb{Z/nZ},b+\mathbb{Z/mZ}).$ Note that this statement is equivalent to: $$c \equiv a \pmod{n}$$ $$c \equiv b \pmod{m}$$

By the Chinese Remainder Theorem, this system has a unique solution c if m and n are coprime.

Answer 3

It's rather more than "related to" the Chinese Remainder Theorem, in fact it really is the CRT, just stated in more abstract terms.

Let $a,b$ be relatively prime and consider the map $$\phi:{\Bbb Z}/ab{\Bbb Z}\to({\Bbb Z}/a{\Bbb Z})\times({\Bbb Z}/b{\Bbb Z}) \quad\hbox{where}\quad \phi(x)=(x\bmod a,x\bmod b)\ .$$ First, this map is well defined: if $x$ has a given value modulo $ab$ then its values modulo $a$ and modulo $b$ are determined, so $\phi(x)$ is uniquely determined. Also, the CRT tells us that if $(s,t)$ in $({\Bbb Z}/a{\Bbb Z})\times({\Bbb Z}/b{\Bbb Z})$ is given then the system $$x\equiv s\pmod a\ ,\quad x\equiv t\pmod b$$ has a solution, so $\phi$ is onto (surjective). Since the domain and codomain have the same size, $\phi$ is a bijection. Finally, it is easy to check (try it) that $$\phi(x+y)=\phi(x)+\phi(y)\ ,$$ and since we are talking about finite sets, this is all we need to show that $\phi$ is an isomorphism.