Euclidean algorithm and GL2(Z) 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)?
 A: 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. 
