Map $\tau(s,t)=(as+bt)\mod{ab}$ is bijection iff $gcd(a,b)=1$

Question

Let $a,b\in\mathbb{Z}^+$. Consider a map $\tau:\mathbb{Z}_a\times\mathbb{Z}_b\to\mathbb{Z}_{ab}$, defined as $\tau(s,t)=(as+bt)\mod{ab}$.
Then, show that $\tau$ is bijection iff $gcd(a,b)=1$.

Here is my attempt for injection:-
Let $(s_1,t_1)\in\mathbb{Z}_a\times\mathbb{Z}_b$ and $(s_2,t_2)\in\mathbb{Z}_a\times\mathbb{Z}_b$, such that
$(as_1+bt_1)\mod{ab}=(as_2+bt_2)\mod{ab}$
$\implies a(s_1-s_2)\mod{ab} + b(t_1-t_2)\mod{ab}=0$
$\implies a(s_1-s_2)\mod{ab}=0$ and $b(t_1-t_2)\mod{ab}=0\space$ ($\because$ sum of two positive numbers)
$\implies s_1=s_2$ and $t_1=t_2$. Hence, $\tau$ is injective.
I think, I have correctly proved injection, however it does not use the GCD assumption.

I am struggling to prove surjection. I have thought like this:
Let $g=gcd(a,b)$. Then, for $a,b\in\mathbb{Z}^+, \forall s,t\in\mathbb{Z}, (as+bt)\in g\mathbb{Z}=a\mathbb{Z}+b\mathbb{Z}$.
$\{(as+bt)\mod{ab}:s,t\in\mathbb{Z}\}=\{mg:m\in\mathbb{Z},0\le mg<ab\}$.
Now, $\forall mg\in\mathbb{Z}_{ab},\exists s,t\in\mathbb{Z}$ such that $mg\mod{ab}=(as+bt)\mod{ab}$.
i.e., $mg\mod{ab}=\tau(s,t)$.
I don't know where and how to use the assumption $g=1$.
Help me!

Answer 1

Using Bézout's identity, the fact that $\gcd(a,b)=1$ implies that there exist $s_1,t_1\in \mathbb{Z}$ such that $1=s_1a+t_1b$.

Given an element $(c\mod ab)\in \mathbb{Z}_{ab}$, you know that $c=c(s_1a+t_1b)=cs_1a+ct_1b$. Then, choose $(s,t)=(ct_1,cs_1)$.

Answer 2

Your injectivity proof is incorrect. The concept of positive numbers does not exist modulo $ab$. Just because $x+y\equiv 0\pmod{ab}$, you cannot conclude $x\equiv 0$ and $y\equiv 0$. For example, $5+7\equiv0\pmod{12}$. Furthermore, the transition from $a(s_1-s_2)\equiv 0$ to $s_1-s_2\equiv 0$ is invalid. It is possible to have nonzero numbers multiply to zero modulo a number, like $3\cdot4\equiv 0\pmod{12}$.

In short, you cannot expect all the usual methods for math in $\mathbb R$ to work in modulo arithmetic.

The best way I can think of involves using Bézout's identity. Choose $x,y$ so that $ax+by=1$. Then, in your correct equation $$ a(s_1-s_2)+b(t_1-t_2)\equiv0\pmod{ab}, $$ multiply both sides by $x$, and substitute $1-by$ in for $ax$. Rearranging, you get $$ (s_1-s_2) \equiv by(s_1-s_2)-bx(t_1-t_2)\pmod{ab} $$ After some thought, this equivalence proves that $s_1-s_2$ is a multiple of $b$. Using a similar method, you can prove $s_1-s_2$ is a multiple of $a$. Since $a$ and $b$ are coprime, this implies that $s_1-s_2$ is a multiple of $ab$, so that $s_1\equiv s_2\pmod{ab}$. Then, a similar method proves that $t_1\equiv t_2\pmod{ab}$.