Proving that a set generates $\Gamma_0(4)$ I want to show that
$$\Gamma_0(4) = \biggl\{\gamma = \pmatrix{a&b\cr c&d}\in {\rm SL}_2({\bf Z}) : 
c\equiv 0\pmod 4\biggr\}$$
is generated by the three matrices
$$\pmatrix{1&1\cr 0&1},\quad\pmatrix{1&0\cr 4&1},\quad\hbox{and}\quad\pmatrix{-1&0\cr 0&-1}.$$
I tried to do this by showing that note that for any $\gamma = \bigl( {a\atop c}{b\atop d}\bigr) \in \Gamma_0(4)$, we have
$$\pmatrix{a&b\cr c&d}\pmatrix{1&-n\cr 0&1} = \pmatrix{a & b-na\cr c&d-nc}\qquad\hbox{and}\qquad
\pmatrix{a&b\cr c&d}\pmatrix{1&0\cr -4n&1} = \pmatrix{a-4nb & b\cr c-4nd&d}.$$
If $c$ is $0$ we are done, since $\gamma$ is in $\Gamma_0(4)$ in this case. Otherwise, if $|c|<|d|$,
we can apply the division
algorithm to get $q$ and $d'$ such that $|d| = |c|q + d'$ with $|d'| < |c|/2$, and the first transformation
applied $q$ times produces a matrix whose bottom-left entry is $c$ and whose bottom-right entry is $d'$. On
the other hand, if
$d\ne 0$ and $|c|>4|d|$, then we can find $q$ and $c'$ such that
$|c| = 4|d|q + c'$ where $|c'| < 2|d|$ and we apply the second transformation $q$ times to get a matrix with bottom-left entry $c'$. In each case, we have strictly reduced the quantity $\min\bigl\{|c|, 2|d|\bigr\}$, so the process must terminate with $|c| = 0$ or $|d|=0$. In the first case we have found an element of $\Gamma_0(4)$, and the second case cannot happen, since it would imply that
$c = \pm 1$.
I think this is the right idea except that we're missing the case where $|d|\le |c|\le 4|d|$ (correct me if there are any other holes in the proof other than this). I'm just not sure what to do in this case.
 A: I have found a roundabout proof that goes through
$$\Gamma(2) = \biggl\{ \pmatrix {a&b\cr c&d} \in {\rm SL}_2({\bf Z}) : a,c\ \hbox{odd},\,b,d\ \hbox{even}\biggr\}.$$
$$\pmatrix{1&2\cr 0&1},\quad\pmatrix{1&0\cr 2&1},\quad\hbox{and}\quad\pmatrix{-1&0\cr 0&-1}$$
To see this, note that for a general matrix $\bigl({a\atop c}{b\atop d}\bigr) \in \Gamma(2)$,
$$\pmatrix{a&b\cr c&d}\pmatrix{1&-2\cr 0&1} = \pmatrix{a & b-2a\cr c&d-2c}\qquad\hbox{and}\qquad
\pmatrix{a&b\cr c&d}\pmatrix{1&0\cr -2&1} = \pmatrix{a-2b & b\cr c-2d&d}.$$
Suppose that $b\ne 0$.
Since $|a|$ is odd and $|b|$ is even, they are not equal. if $|a|$ is larger, we use the division algorithm
to find $q,r$ such that $|a| = |2b|q+r$, where $|r| < |b|$, and then apply the second transformation $q$
times to strictly reduce the absolute value of the top-left matrix entry. If $|b|$ is larger, we reduce
the absolute value of the top-right entry in a similar fashion. We can keep doing this until $b=0$, in which
case the matrix must be some integer power of $\bigl( {1\atop 2}{0\atop 1}\bigr)$, after possibly multiplying by
$\bigl( {-1\atop 0}{0\atop-1}\bigr)$.
Now we claim that $\Gamma(2)$ and $\Gamma_0(4)$ are conjugate in ${\rm SL}_2({\bf Q})$, by the element $\bigl( {2\atop 0}{0\atop 1}\bigr)$. Indeed,
for any $\gamma = \bigl({a\atop c}{b\atop d}\bigr) \in {\rm SL}_2({\bf Z})$,
$$\pmatrix{ 1/2 & 0\cr 0&1} \pmatrix {a&b\cr c&d}\pmatrix{2&0\cr 0&1} = 
\pmatrix{ a/2 & b/2\cr 0&1}\pmatrix{2&0\cr 0&1} = \pmatrix{a&b/2\cr 2c&d},$$
and if $\gamma\in \Gamma(2)$ to begin with, then $2c$ is a multiple of $4$ so the result is in $\Gamma_0(4)$. On the other hand,
$$\pmatrix{ 2 & 0\cr 0&1} \pmatrix {a&b\cr c&d}\pmatrix{1/2&0\cr 0&1} = 
\pmatrix{ 2 & b\cr 0&1}\pmatrix{1/2&0\cr 0&1} = \pmatrix{a&b\cr c/2&d}.$$
In this case, if $\gamma\in \Gamma_0(4)$, then $bc$ is even so $a$ and $d$ must be odd for $ad-bc$ to equal $1$. Since $c$ was a multiple of $4$, we have $c/2$ even and of course, so is $2b$, so the result is in $\Gamma(2)$.
Finally, note that
$$\pmatrix{ 1/2 & 0\cr 0&1} \pmatrix {1&2\cr 0&1}\pmatrix{2&0\cr 0&1} = \pmatrix{ 1&1\cr 0&1}$$
and
$$\pmatrix{ 1/2 & 0\cr 0&1} \pmatrix {1&0\cr 2&1}\pmatrix{2&0\cr 0&1} = \pmatrix{ 1&0\cr 4&1},$$
so the generators of $\Gamma_0(4)$ are indeed
$$\pmatrix{1&1\cr 0&1},\quad\pmatrix{1&0\cr 4&1},\quad\hbox{and}\quad\pmatrix{-1&0\cr 0&-1}.$$
I will leave the question open, in the hope that someone can bring my original approach to a conclusion or show that something is wrong with it. Thanks!
