Surjective map from $\mathrm{SL}(2, \mathbb{Z})$ to $\mathrm{SL}(2,\mathbb{Z}/n\mathbb{Z})$

Question

Can anyone refer me to a complete proof of that there exist such surjective maps?

I looked this up and in these notes the part of showing $b'$ exist is omitted. I still haven't figured out how to show, for example, $(b+x·(a,n),a)=1$ can be solved for $x$ when $(a,b,n)=1$.

Thank you!

Edit: I'm not sure how to show that taking all coefficients $\bmod n$ will give you a surjective map. In Conrad's notes from the link above, one step is omitted: given three integers $a,b,n$ such that $\gcd(a,b,n)=1$, there must exist an integer $b'$ such that $b'\equiv b \bmod n$ and $b'$ is coprime with $a$.

If there is another way of showing that the $\bmod n$ map is surjective, I'd like to hear about that, too.

Answer 1

Here is a very general technique (more than you asked for). Let $A$ be any commutative ring with 1 and let $SL_n(A)$ be the $n\times n$ matrices of determinant one. This has a natural subgroup called $E_n(A)$ generated by the matrices coming from row and column operations, called the group of elementary matrices. If $A\to B$ is surjective, then $E_n(A)\to E_n(B)$ can easily seen to be surjective, since the elements are generated by matrices of the form one on the diagonal and at most one non-zero entry off the diagonal. It is easy to check that $SL_n(\mathbb{Z})=E_n(\mathbb{Z})$ for all $n$ and the same is true when you replace $\mathbb{Z}$ by $\mathbb{Z}/m\mathbb{Z}$. So, you are done.

This edit is to answer questions of darij grinberg below. Two situations when $SL_n=E_n$ is when the ring is a Euclidean domain (like integers) or it is semilocal (like $\mathbb{Z}/m\mathbb{Z}$). Let me explain this for integers, other cases being similar and $SL_2$, (for $SL_n, n\geq 3$, PID would be enough).

So take $\sigma\in SL_2(\mathbb{Z})$. Let its first row be $(a,b)$. Then by column operations (no switching, no scaling), one can make $a,b\geq 0$. Then by division algorithm, one can make one of them to be zero, keeping both non-negative. Then the row is of the form $(1,0)$ or $(0,1)$. If it is $(0,1)$, again column operations would make it into $(1,0)$. Now $\sigma$ is lower triangular, but being in $SL_2$, it has ones on the diagonal. Rest is easy.

Answer 2

The problem: Let $A\in M_2(\mathbb{Z})$ such that $\det A \equiv 1 \pmod n$. To find $A' \in M_2(\mathbb{Z})$ such that $A'\equiv A \pmod n$, and $\det A'=1$.

Use Smith Normal form to write $A$ as $$A = U D V$$ with $U$, $V$ of $\det 1$, and $D$ diagonal with $(d_1,d_2)$ on the diagonal. Taking determinants we get $d_1d_2 \equiv 1 \pmod n$, so there exist $k$ so that $d_1 d_2 = 1 + k n$. Now consider $A' = U D' V$ with $D'= \left (\begin{matrix} d_1 & -kn \\ kn & d_2(1-kn)\end{matrix}\right)$. We have $\det A'=1$ and $A'\equiv A \pmod n$