7
$\begingroup$

I am trying to prove that the the natural map from the special linear group $\operatorname{SL}_2(\mathbb{Z})$ to the special linear group $\operatorname{SL}_2(\mathbb{Z}/n\mathbb{Z})$ is surjective. Clearly, the problem lies in finding an inverse with determinant one. If have following outline of a proof :

Pick a matrix $\big(\begin{smallmatrix}a &b \\c& d\end{smallmatrix}\big)\in \operatorname{SL}_2(\mathbb{Z}/n\mathbb{Z})$. Use the Chinese remainder theorem to find $b'=b \text{ mod } n$ such that $a$ and $b$ are relatively prime... Once I have this I can find an inverse.

The problem is that I cannot figure out how the Chinese remainder theorem could be of use, since there is no reason to assume $a$ and $n$ (capital $N$ in proof) have ggd=1.

If so one could say there is a solution of $b'=b \bmod N$ and $b'= 1 \bmod a$.

But I fail to see how they do it in general.

Many thanks!

2 Answers 2

3

Define the subsets $S$ and $T$ of $\text{M}_2(\mathbb Z)$ by

$\bullet\ A\in S\iff A\equiv g\bmod n$ for some $g$ in $\text{SL}_2(\mathbb Z)$ depending on $A$,

$\bullet\ A\in T\iff\det(A)\equiv1\bmod n$.

In particular $$ G:=\text{SL}_2(\mathbb Z)\subset S\subset T\subset\text{M}_2(\mathbb Z). $$ We must show $S=T$.

Clearly

$\bullet\ G\times G$ act on $S$ and $T$ by $$ (g,h)A=gAh^{-1}, $$ $\bullet$ for each $A$ in $T$ there are $g,h\in G$ such that $gAh^{-1}$ is diagonal.

Thus, it suffices to show that any $\text{diag}(a,d)\in T\ $ belongs to $S$.

It is straightforward to check that, as Alex Youcis noticed, there are integers $c'$ and $d'$ satisfying $$ S\ni \begin{pmatrix}a&n\\c'&d'\end{pmatrix}\equiv \begin{pmatrix}a&0\\0&d\end{pmatrix}\bmod n. $$ The general lemma is:

If $a,b,n$ are integers such that $\gcd(a,b)=1$, then any solution mod $n$ to $$ ax+by=1\tag1 $$ lifts to an exact solution. That is, if $x_0$ and $y_0$ satisfy $$ ax_0+by_0\equiv1\bmod n, $$ then there is a solution to $(1)$ such that $$ x\equiv x_0,\quad y\equiv y_0\quad\bmod n. $$

  • 0
    Thanks @Pierre-Yves Gaillard ! Do you mean by diagonal that b=0=c? Then I still believe you need gcd(a,n)=1 before b' exists? Am I missing something in that reasoning? The actions on S I find strange. Is S the set of matrices congruent to a specific element. If so after multiplication one cannot expend to remain in S, no ?2011-12-29
  • 0
    Dear @MrOperator: Thanks! (1) Yes, by diagonal I mean $b=0=c$. (2) $\gcd(a,n)=1$ follows from $ad\equiv1\bmod n$. (3) I'll edit to clarify the definition of $S$, but before doing that I'd like to make sure with you that everything is OK. So, an $A\in\text{M}_2(\mathbb Z)$ is in $S$ iff there is a $g\in G$ such that $A\equiv g\bmod n$. - Thanks in advance for letting me know if the argument looks correct to you.2011-12-29
  • 0
    Hi @Pierre-Yves Gaillard! This does look correct on first sight. I will meditate some more tonight and tomorrow during the day. I will definitely let something know, but thanks already!2011-12-29
  • 0
    Dear @MrOperator: I made a few changes (and Dylan corrected a typo).2011-12-30
10

You're basically right. Take an arbitrary $\left(\begin{smallmatrix}a & b\\ c & d\end{smallmatrix}\right)\in\text{SL}_2(\mathbb{Z}_n)$. Choose then $b'\equiv b\text{ mod }n$ such that $(b',a)=1$ (this is where you use CRT). Since $(b',a)=1$ Bezout's lemma tells you that there exists $x,y\in\mathbb{Z}$ with $ax-b'y=1$ let then $c'=c+y(1-(ad-b'c))$ and $d'=d+x(1-(ad-b'c))$. Then, $ \left(\begin{smallmatrix}a & b'\\ c' & d'\end{smallmatrix}\right)\in\text{SL}_2(\mathbb{Z})$ and easily verified to have image under the canonical map equal to what we want.

  • 1
    That should probably be $d'=d+\cdots$.2011-12-28
  • 5
    Indeed it was. Thank you oh so aptly named friend.2011-12-28
  • 0
    Yes indeed that was what I had in mind. However (mayby my post was a bit confusing) my problem lies in the application of th CRT. One doesn't know the ggd of a and n is one. Therefore I don't quite see how to use the CRT. I can't say b′=b mod n and b′=1 mod a.2011-12-28
  • 0
    Dear @AlexYoucis: I'm afraid your $b'$ doesn't exist if, for instance, $a=0,b=2,n=5$.2011-12-29
  • 0
    Indeed, I suppose a=0 must be treated separately. However if $a=kN$ doesn't this leave enough freedom on $d$ to find a solution? Say a is not zero. Then I presume b' can be found by saying. $b'=b \text{ mod } N$ and $b'=1 \text{ mod } a$ and $b'=1 \text{ mod } gcd(a,N)$. Ou of these conditions one finds if a solution exists $b=1 \text{ mod } gcd(a,N)$. But this doesn't ensure a solution. Am I using Thc CRT wrong, since I cannot even figure out @AlexYoucis would use the CRT.2011-12-29
  • 0
    Dear @AlexYoucis: I posted another answer.2011-12-30