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

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.

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}$$