Proving a bijection from $ (\mathbb{Z}/ab\mathbb{Z})^\times$ to $(\mathbb{Z}/a\mathbb{Z})^\times \times (\mathbb{Z}/b\mathbb{Z})^\times$

Question

Show that the function

$$ (\mathbb{Z}/ab\mathbb{Z})^\times \to (\mathbb{Z}/a\mathbb{Z})^\times \times (\mathbb{Z}/b\mathbb{Z})^\times $$

defined by $f([x]_{ab})=([x]_a,[x]_b)$ is a bijection where $\gcd(a,b)=1$.

I am trying to show this by proving injectivity and surjectivity, but am not sure if that is the best way. For injectivity, I am trying to show that $f([x]_{ab})=f([y]_{ab})\implies [x]_a=[y]_a, [x]_b=[y]_b$. Am I going about this in the right way. Any suggestions would be greatly appreciated.

Answer 1

Suppose $x\equiv y \bmod{a}$ and $x\equiv y \bmod{b}$.

Then $x-y=ta$, $x-y=sb$, hence $ta=sb$.

Since $gcd(a,b)=1$, what's the relation between $b$ and $t$?

Answer 2

It is possible to show that $f$ is both injective and surjective, where $$ \begin{align} f: (\mathbb{Z}/ab\mathbb{Z})^\times &\longrightarrow (\mathbb{Z}/a\mathbb{Z})^\times \times (\mathbb{Z}/b\mathbb{Z})^\times \\ f([x]_{ab}) &= ([x]_a, [x]_b), \end{align}$$ where $\gcd(a,b) = 1$ and we use $[x]_a$ to indicate a congruence class modulo $a$.

---

Injectivity

Suppose that $f([x]_a) = f([y]_b)$. This necessarily means that $[x]_a = [y]_a$ and $[x]_b = [y]_b$, or equivalently that $x \equiv y \bmod a$ and $x \equiv y \bmod b$. If $x \equiv y \bmod a$, then $a \mid (x - y)$. Similarly, we have $b \mid (x-y)$.

Since $a \mid (x-y)$ we can write $(x-y) = ak$ for some $k$. In this form, the statement that $b \mid (x-y)$ can be rewritten as $b \mid ak$.

Lemma: Let $a,b,c$ be integers. If $a \mid bc$ and $\gcd(a,b) = 1$, then $a \mid c$.

Proof: This is the content of this question.

By this lemma, we see that since $\gcd(b,c) = 1$, we must have that $b \mid k$. Thus $(x-y) = ak = ab k'$ for some integer $k'$. But then $ab \mid (x-y)$ and we have that $[x]_{ab} = [y]_{ab}$, which says that $x$ and $y$ are actually the same (mod $ab$).

We have shown that $f(x) = f(y)$ implies that $x \equiv y \pmod{ab}$, proving injectivity. $\square$

---

Surjectivity

Given an ordered pair $([x]_a,[y]_b) \in (\mathbb{Z}/a\mathbb{Z})^\times \times (\mathbb{Z}/b\mathbb{Z})^\times$, we want to find $[z]_{ab} \in (\mathbb{Z}/ab\mathbb{Z})^\times$ such that $f([z]_{ab}) = ([x]_a,[y]_b)$. For simplicity, let's fix representatives $x,y,z$ for the congruence classes mod $a,b$, and $ab$ (respectively).

Lemma: Let $a,b$ be integers with $\gcd(a,b) = 1$. Then there are integer solutions to the linear equation $aX + bY = 1$.

Proof: This is described at the bottom of this answer or in many answers to this question, and in some of the linked questions there. This is frequently called the major application of the "extended Euclidean algorithm".

As $\gcd(a,b) = 1$, we know that there is a solution to $aX + bY = 1$. Since such an $X$ will necessarily satisfy $aX \equiv 1 \bmod b$ and $bY \equiv 1 \bmod a$, I choose to denote such an integer $X$ as $[a]^{-1}_b$ and to denote $Y$ as $[b]^{-1}_a$. By a minor abuse of notation, I use the symbols $[a]^{-1}_b$ and $[b]^{-1}_a$ to mean integers (instead of congruence classes).

The claim is that we can choose $z = y a[a]^{-1}_b + x b[b]^{-1}_a$.

Indeed, looking at $z \bmod a$, we see that the first term vanishes since it's clearly divisible by $a$. And as $b [b]^{-1}_a \equiv 1 \bmod a$ (in fact, this is the defining attribute of $[b]^{-1}_a$), we see that $z \equiv x \bmod a$. Similarly, $z \equiv y \bmod b$. It's clear that adding multiples of $ab$ to $z$ doesn't change its image under $f$, so indeed $[z]_{ab}$ is a residue class such that $f([z]_{ab}) = ([x]_a, [y]_b)$.

And thus $f$ is surjective. $\square$

---

Additional Notes

This is an elementary proof of a result called the Chinese Remainder Theorem. (In fact, a very similar proof appears in an elementary number theory course I taught for several years).

The surjectivity proof uses an idea that is very similar to the fundamental idea of Lagrange polynomial interpolation. In fact, Lagrange polynomial interpolation is exactly the Chinese remainder theorem over polynomial rings.

There is a different way of viewing the consideration of surjectivity. Above, we did that above by constructing $z$ from $x$ and $y$. But one can instead think of constructing $z$ from $x$ and $y$ as follows.

We find all integer solutions $z$ to the pair of congruences $z \equiv x \bmod{a}$ and $z \equiv y \bmod{b}$. Rewrite $z \equiv x \bmod a$ as $z = x + ak$ for integers $k$, and substitute into $z \equiv y \bmod {b}$ to get $$ x + ak \equiv y \bmod b.$$ In this congruence equation, everything except $k$ is fixed, so we rewrite it as $$ k \equiv a^{-1} (y - x) \bmod b.$$ That $a^{-1} \bmod b$ exists is a consequence of the lemma in the surjectivity section above. As above, I will write $a^{-1}$ to mean an integer representative of the congruence class modulo $b$. Then $k = a^{-1} (y-x) + b \ell$ for integers $\ell$. Substituting back into $z = x + ak$ shows that $z = x + a(a^{-1}(y-x)) + ab\ell$ for integers $\ell$.

Thus $z \equiv x + a(a^{-1}(y-x)) \bmod {ab}$, and there is a unique solution to the pair of congruence equations mod $ab$. This uniqueness corresponds to the injectivity of $f$, and the surjectivity corresponds to the existence of $z$. $\spadesuit$