[proofplan] We first verify the displayed relations by direct multiplication. For generation, we let $H := \langle S,T\rangle$ and prove that the left action of $H$ on primitive integer column vectors can reduce every first column of a matrix in $SL_2(\mathbb{Z})$ to $(\pm 1,0)^\top$. Once the first column is reduced, the determinant condition forces the reduced matrix to be either a power of $T$ or $-1$ times a power of $T$, both of which lie in $H$. This shows the original matrix lies in $H$, and the statement for $PSL_2(\mathbb{Z})$ follows by passing to the quotient. [/proofplan]

[step:Verify the two matrix relations by multiplication] We compute \begin{align*} S^2 &= \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} = -I. \end{align*} Next, \begin{align*} ST &= \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix}, \\ (ST)^2 &= \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} -1 & -1 \\ 1 & 0 \end{pmatrix}, \\ (ST)^3 &= \begin{pmatrix} -1 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} = -I. \end{align*} Thus $S^2 = (ST)^3 = -I$. [/step]

[step:Reduce every primitive integer column vector using $S$ and powers of $T$]Let $H := \langle S,T\rangle$ be the subgroup of $SL_2(\mathbb{Z})$ generated by $S$ and $T$. Since $T \in H$, every integer power $T^q$ with $q \in \mathbb{Z}$ belongs to $H$. [claim:Primitive column reduction] For every pair $(a,c) \in \mathbb{Z}^2$ with $\gcd(a,c)=1$, there exist $w \in H$ and $\varepsilon \in \{1,-1\}$ such that \begin{align*} w \begin{pmatrix} a \\ c \end{pmatrix} = \begin{pmatrix} \varepsilon \\ 0 \end{pmatrix}. \end{align*} [/claim] [proof] For $q \in \mathbb{Z}$, multiplication by $T^q$ and by $S$ gives \begin{align*} T^q \begin{pmatrix} a \\ c \end{pmatrix} &= \begin{pmatrix} 1 & q \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a \\ c \end{pmatrix} = \begin{pmatrix} a+qc \\ c \end{pmatrix}, \\ S \begin{pmatrix} a \\ c \end{pmatrix} &= \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a \\ c \end{pmatrix} = \begin{pmatrix} -c \\ a \end{pmatrix}. \end{align*} If $c=0$, then $\gcd(a,0)=1$ forces $a \in \{1,-1\}$, and the claim holds with $w=I$. Assume $c \neq 0$. Choose $q \in \mathbb{Z}$ and $r \in \mathbb{Z}$ such that \begin{align*} r = a + qc, \qquad |r| < |c|. \end{align*} This is the Euclidean division step applied to $a$ modulo $c$, with the sign absorbed into the choice of $q$. Then \begin{align*} S T^q \begin{pmatrix} a \\ c \end{pmatrix} = S \begin{pmatrix} r \\ c \end{pmatrix} = \begin{pmatrix} -c \\ r \end{pmatrix}. \end{align*} The new second coordinate has absolute value $|r|$, strictly smaller than the old absolute value $|c|$. Repeating this reduction produces a finite sequence because the non-negative integer $|c|$ strictly decreases at each non-terminal stage. The process stops when the second coordinate is $0$. Throughout the process the matrices used are products of $S$ and integer powers of $T$, hence lie in $H$. The greatest common divisor of the two coordinates is preserved by multiplication by $S$ and by $T^q$, since these matrices are invertible over $\mathbb{Z}$. Therefore the terminal vector has the form $(\varepsilon,0)^\top$ with $\varepsilon \in \{1,-1\}$. This proves the claim. [/proof][/step]

[guided]Let $H := \langle S,T\rangle$. The reduction is the Euclidean algorithm written in matrix language. The matrix $T^q$ performs the elementary row operation \begin{align*} (a,c)^\top \mapsto (a+qc,c)^\top, \end{align*} while $S$ swaps the two entries up to a sign: \begin{align*} (a,c)^\top \mapsto (-c,a)^\top. \end{align*} Both operations preserve the greatest common divisor because they are invertible integer linear transformations. We prove the precise reduction statement. Let $(a,c) \in \mathbb{Z}^2$ satisfy $\gcd(a,c)=1$. If $c=0$, then $\gcd(a,0)=|a|=1$, so $a=\varepsilon$ for some $\varepsilon \in \{1,-1\}$, and the identity matrix already sends $(a,c)^\top$ to $(\varepsilon,0)^\top$. Now suppose $c \neq 0$. Choose integers $q$ and $r$ such that \begin{align*} r = a+qc, \qquad |r| < |c|. \end{align*} This is exactly the Euclidean step: we replace $a$ by a remainder modulo $c$ whose absolute value is smaller than $|c|$. Applying $T^q$ first and then $S$ gives \begin{align*} S T^q \begin{pmatrix} a \\ c \end{pmatrix} = S \begin{pmatrix} a+qc \\ c \end{pmatrix} = S \begin{pmatrix} r \\ c \end{pmatrix} = \begin{pmatrix} -c \\ r \end{pmatrix}. \end{align*} The important feature is that the second coordinate has changed from $c$ to $r$, and $|r|<|c|$. Thus repeated application of this operation must terminate, because there is no infinite strictly decreasing sequence of non-negative integers. At the terminal stage the second coordinate is $0$. Since every step was multiplication by a matrix in $H$, the total product is some $w \in H$. Since every step is invertible over $\mathbb{Z}$, the greatest common divisor remains $1$, so the terminal vector must be $(1,0)^\top$ or $(-1,0)^\top$. Hence there exist $w \in H$ and $\varepsilon \in \{1,-1\}$ such that \begin{align*} w \begin{pmatrix} a \\ c \end{pmatrix} = \begin{pmatrix} \varepsilon \\ 0 \end{pmatrix}. \end{align*}[/guided]

[step:Use column reduction to express an arbitrary determinant-one matrix as a word in $S$ and $T$]Let \begin{align*} \gamma := \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in SL_2(\mathbb{Z}). \end{align*} The determinant condition gives \begin{align*} ad-bc = 1. \end{align*} Hence every common divisor of $a$ and $c$ divides $ad-bc=1$, so $\gcd(a,c)=1$. By the primitive column reduction claim, choose $w \in H$ and $\varepsilon \in \{1,-1\}$ such that \begin{align*} w \begin{pmatrix} a \\ c \end{pmatrix} = \begin{pmatrix} \varepsilon \\ 0 \end{pmatrix}. \end{align*} Since the first column of $w\gamma$ is $w(a,c)^\top$, there exist integers $n$ and $\delta$ such that \begin{align*} w\gamma = \begin{pmatrix} \varepsilon & n \\ 0 & \delta \end{pmatrix}. \end{align*} Because $w,\gamma \in SL_2(\mathbb{Z})$, their product has determinant $1$. Therefore \begin{align*} 1 = \det(w\gamma) = \varepsilon \delta, \end{align*} so $\delta=\varepsilon$. Thus \begin{align*} w\gamma = \begin{pmatrix} \varepsilon & n \\ 0 & \varepsilon \end{pmatrix}. \end{align*} If $\varepsilon=1$, then \begin{align*} w\gamma = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix} = T^n \in H. \end{align*} If $\varepsilon=-1$, then \begin{align*} w\gamma = \begin{pmatrix} -1 & n \\ 0 & -1 \end{pmatrix} = -S^0T^{-n} = (-I)T^{-n} = S^2T^{-n} \in H, \end{align*} where we used $S^2=-I$. In both cases $w\gamma \in H$. Since $w \in H$ and $H$ is a subgroup, $w^{-1} \in H$, and therefore \begin{align*} \gamma = w^{-1}(w\gamma) \in H. \end{align*} Because $\gamma \in SL_2(\mathbb{Z})$ was arbitrary, $SL_2(\mathbb{Z}) \subset H$. The reverse inclusion $H \subset SL_2(\mathbb{Z})$ holds from the definition of $H$ as a subgroup generated by elements of $SL_2(\mathbb{Z})$. Hence \begin{align*} SL_2(\mathbb{Z}) = H = \langle S,T\rangle. \end{align*}[/step]

[guided]Let \begin{align*} \gamma := \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in SL_2(\mathbb{Z}). \end{align*} We want to prove that $\gamma$ is a word in $S$ and $T$. The first column is the place to start because the determinant equation \begin{align*} ad-bc=1 \end{align*} implies $\gcd(a,c)=1$: any integer dividing both $a$ and $c$ also divides $ad$ and $bc$, hence divides $ad-bc=1$. The primitive column reduction claim applies to $(a,c)$. Thus there are $w \in H$ and $\varepsilon \in \{1,-1\}$ such that \begin{align*} w \begin{pmatrix} a \\ c \end{pmatrix} = \begin{pmatrix} \varepsilon \\ 0 \end{pmatrix}. \end{align*} Since multiplying $\gamma$ on the left multiplies each column by $w$, the first column of $w\gamma$ is $(\varepsilon,0)^\top$. Hence $w\gamma$ has the form \begin{align*} w\gamma = \begin{pmatrix} \varepsilon & n \\ 0 & \delta \end{pmatrix} \end{align*} for some $n,\delta \in \mathbb{Z}$. Now the determinant condition determines the lower-right entry. Since $w$ and $\gamma$ both have determinant $1$, the product $w\gamma$ also has determinant $1$. Therefore \begin{align*} 1=\det(w\gamma)=\varepsilon \delta. \end{align*} Because $\varepsilon \in \{1,-1\}$, this forces $\delta=\varepsilon$. Thus \begin{align*} w\gamma = \begin{pmatrix} \varepsilon & n \\ 0 & \varepsilon \end{pmatrix}. \end{align*} There are two cases. If $\varepsilon=1$, then \begin{align*} w\gamma = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix} = T^n, \end{align*} which lies in $H$. If $\varepsilon=-1$, then \begin{align*} w\gamma = \begin{pmatrix} -1 & n \\ 0 & -1 \end{pmatrix} = (-I) \begin{pmatrix} 1 & -n \\ 0 & 1 \end{pmatrix} = S^2T^{-n}, \end{align*} which also lies in $H$, because $S^2=-I$ and $T^{-n} \in H$. Thus $w\gamma \in H$. Since $w \in H$ and $H$ is a subgroup, $w^{-1} \in H$, so \begin{align*} \gamma = w^{-1}(w\gamma) \in H. \end{align*} This proves every element of $SL_2(\mathbb{Z})$ lies in $H$. Since $H$ was generated by elements already in $SL_2(\mathbb{Z})$, we conclude \begin{align*} SL_2(\mathbb{Z})=\langle S,T\rangle. \end{align*}[/guided]

[step:Pass the generators and relations to $PSL_2(\mathbb{Z})$] Let \begin{align*} \pi: SL_2(\mathbb{Z}) \to PSL_2(\mathbb{Z}) \end{align*} be the quotient homomorphism, and define \begin{align*} \bar{S} := \pi(S), \qquad \bar{T} := \pi(T). \end{align*} Since $SL_2(\mathbb{Z})=\langle S,T\rangle$ and $\pi$ is surjective, every element of $PSL_2(\mathbb{Z})$ is a word in $\bar{S}$ and $\bar{T}$. Hence \begin{align*} PSL_2(\mathbb{Z})=\langle \bar{S},\bar{T}\rangle. \end{align*} Applying the homomorphism $\pi$ to the relations $S^2=(ST)^3=-I$ gives \begin{align*} \bar{S}^2 = \pi(S)^2 = \pi(S^2) = \pi(-I) = \pi(I), \end{align*} and \begin{align*} (\bar{S}\bar{T})^3 = \pi(ST)^3 = \pi((ST)^3) = \pi(-I) = \pi(I). \end{align*} Therefore \begin{align*} \bar{S}^2=(\bar{S}\bar{T})^3=\pi(I), \end{align*} which is the identity element of $PSL_2(\mathbb{Z})$. This completes the proof. [/step]