On the generators of the Modular Group The modular group is the group $G$ consisting of all linear fractional transformations $\phi$ of the form
$$\phi(z)=\frac{az+b}{cz+d}$$
where $a,b,c,d$ are integers and $ad-bc=1$. I have read that $G$ is generated by the transformations $\tau(z)=z+1$ and $\sigma(z)=-1/z$. Is there an easy way to prove this? In particular, is there a proof that uses the relation between linear fractional transformations and matrices? Any good reference would be helpful.
Thank you,
Malik 
 A: Here is an elementary proof (not necessarily easy).
We consider 3 cases:
(i) If $a=0$, then $bc=-1$, so $b=-c=\pm 1$ therefore $\phi(z)=\frac{\pm 1}{\mp z+ d}=\sigma\tau^{\mp d}(z)$.
(ii) If $|a|=1$. Since $\frac{-az-b}{-cz-d}=\frac{az+b}{cz+d}$, we may just assume $a=1$, so that  $d-bd=1$. Notice that:
$$\phi(z)=\frac{z+b}{cz+d}\stackrel{\sigma}{\longrightarrow}\frac{-cz-d}{z+b}\stackrel{\tau^c}{\longrightarrow}-\frac{1}{z+b}$$
Therefore $\sigma\tau^c\phi(z)=-\frac{1}{z+b}$, which brings us back to case (i).
(iii) If $|a|>1$, we will show that we can reduce it to case (ii).
The idea is to modify $\phi$ to get a new $\phi_1(z)=\frac{a_1z+b_1}{c_1z+d_1}$ with $|a_1|<|a|$ and $|c_1|<|c|$. If this is possible, then $|a_1|$ gets closer to $1$ so, repeating the process, we eventualy get $\phi_n$ with $|a_n|=1$.
Let's define $\phi_1$. First, we assume $|a|>|c|$ (otherwise, just consider $\sigma\phi$ instead of $\phi$). Now take a convenient $n\in\mathbb{Z}$ so that $|a-nc|$ smaller then both $|a|$ and $|c|$ (this is exactely the closest integer $n:=\left[\frac{a}{c}\right]$). The term $a-nc$ appears by appling $\tau^{-n}$:
$$\tau^{-n}\phi(z)=\frac{(a-nc)z+(b-nd)}{cz+d}$$
We then apply $\sigma$ so that $(a-nc)$ and $c$ switch places (modulo a $-1$ sign), so $\phi_1(z):=\sigma\tau^{-n}\phi(z)$ is exactely what we need.
A: Yes; this statement is essentially equivalent to the Euclidean algorithm.  I discuss these issues in this old blog post.  (A very brief sketch: by applying the generators and the inverses to an arbitrary element of the modular group it is possible to perform the Euclidean algorithm on $a$ and $c$ (or maybe it's $a$ and $b$).  The rest is casework.)  You can think of this as a form of row reduction, which is generalized by the notion of Smith normal form.
There is also a geometric proof using the action on the upper half plane which is given, for example, in the relevant section of Serre's Course in Arithmetic.
