Euclidean algorithm and GL2(Z)

Question

How can I use the Euclidean algorithm to prove the matrices $$ \begin{pmatrix} 1&1\\ 0&1\\ \end{pmatrix} \begin{pmatrix} 0&1\\ 1&0\\ \end{pmatrix} $$ are generating GL(2,Z)?

Answer 1

Denote the first matrix u, and the second v. You have, then that $ u^n= \left[ {\begin{array}{cc} 1 & n \\ 0 & 1\\ \end{array} } \right], n\in \mathbb{Z} $ and $v^{2n}=I_2$ (you can prove it by induction). You can also show that you can generate all the matrices of the form $\left[ {\begin{array}{cc} 0 & 1 \\ 1 & n\\ \end{array} } \right],\left[ {\begin{array}{cc} 1 & 0 \\ n & \pm1\\ \end{array} } \right]$.

Now, if we have a matrix in $\left[ {\begin{array}{cc} a & b \\ c & d\\ \end{array} } \right]\in GL_2(\mathbb{Z})$ , then write $a=q\cdot b +r$.

Now we can put: $$ \left[ {\begin{array}{cc} a & b \\ c & d\\ \end{array} } \right]\cdot \left[ {\begin{array}{cc} 0 & 1 \\ 1 & -r\\ \end{array} } \right]= \left[ {\begin{array}{cc} b & a-br \\ c' & d'\\ \end{array} } \right]=\left[ {\begin{array}{cc} b & r \\ c' & d'\\ \end{array} } \right] $$ Continue to multiply with the corresponding q. Eventually, you will get the matrix $ \left[ {\begin{array}{cc} gcd(a,b) & 0 \\ c'' & d''\\ \end{array} } \right] $ But as we know, $det\left[ {\begin{array}{cc} a & b \\ c & d\\ \end{array} } \right]=ad-bc=\pm1$. So we can write a linear combination of $a,b$ that is equal to 1, so $gcd(a,b)=1$. So the matrix we got is: $\left[ {\begin{array}{cc} 1 & 0 \\ c'' & d''\\ \end{array} } \right]$ and it's determinant is still $\pm 1$, so, $d''=\pm1$. But we showed that we can generate this matrix, so we finished.