I came across Shimura (1971) notes about cosets representatives of the congruence subgroups $ \Gamma_0(N) $. He firstly proves that its index in the modular group $\Gamma$ is
\begin{equation} [\Gamma : \Gamma_0(N)]=N \cdot \prod_{p|N} (1+p^{-1} ) \end{equation}
Then he comes up with a sets of cosets representatives for $\Gamma_0(N)$ in $\Gamma$ made in this way: we first choose pairs $(c,d)$ of positive integers such that
\begin{equation} (c,d)=1, \qquad d|N, \qquad 0 < c \le N/d \end{equation}
then for each pairs we fix integers $a,b$ such that $ad-bc=1$. Our list of cosets representatives is made of the matrices with such entries.
However, let us take for example $N=12$ when we know the index is 24 and thus this is the cardinality of the set of cosets representatives.
Using the rule above, I only find 22 cosets representatives, namely the ones corresponding to the following $(c,d)$ pairs: $$(1,1),(2,1),\dots,(12,1),(1,2),(3,2),(5,2),(1,3),(2,3),(4,3),(1,4),(3,4),(1,6),(1,12).$$
I also tried to run SAGE and it gives me 24 cosets representatives but they seem redundant, for example $[[1, 0] [2, 1]]$ and $[[1, 2][2, 5]]$ are listed as different cosets representatives, but
$$\begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 2 \\ 2 & 5 \end{pmatrix}$$
and thus it seems to me that these 2 matrices belong in fact to the same coset.
Something is clearly wrong, I hope you can help me.
Best Answer
Here is another attempt, this time hopefully with a correct answer. First off, the problem gets worse for e.g. N=24, where the index is 48, yet we only get 44 coset representatives.
For $N=12$, representatives for the two missing cosets are for example $(1,9)=(5,9)=(7,3)=(11,3)$ and $(1,8)=(5,4)=(7,8)=(11,4)$ (here with equality I mean that the pairs represent the same coset).
To find these, I first claim that there is a natural bijection beween $\Gamma/\Gamma_0(N)$ and the "projective line" $P^1(R)$, where $R:=\mathbb{Z}/N\mathbb{Z}$, which consists of the "1-dimensional subspaces of $R^2$". That is, subsets of $R^2$ of the form $(c,d) \cdot R^\times$ and of size $\lvert R^\times \rvert$. Indeed, it is easy to very that $\Gamma$ acts transitively (say, from the right) on $P^1(R)$, and the stabilizer of $(0,1)\cdot R^\times$ then equals $\Gamma_0(N)$. The claim follows.
Thus we just have to find representatives for the orbits $A:=(c,d)\cdot R^\times$ of $P^1(R)$. If $d$ is a unit, we can divide by $d$ and thus we certainly can choose the pairs $(c,1)$ as one type of coset representative. It remains to consider the pairs $(c,d)$ where $d$ is not a unit. Note that we may choose $1\leq c,d\leq N$ such that $gcd(c,d)=1$ (for either the gcd is invertible mod $N$, and so we can divide it out; or else it is a non-unit $x$, but then $x\cdot R^\times$ is strictly smaller than $R^\times$, and so $A$ is not an element of $P^1(R)$).
Looking at the formula you give (and attribute to Shimura), this is exactly what happens there: The element $d$ is either 1, or else $gcd(d,N)\neq 1$, in which case $d$ corresponds to a non-unit of $R$; one can in fact show that the $R^\times$-orbits (action by multiplication) on $R$ have the divisors of $N$ as representants.
However, the formula you describe is then to restrictive on what values for $c$ are used. Unfortunately, I cannot tell you a good closed formula as alternative right now, but with the above description, it is still relatively easy to compute representatives for all orbits: Let $d$ vary as described, but then do not only consider $c\leq N/d$, but rather study the orbits of $Stab_{R^\times}(d)$ on $R$ to find all possible values for $c$. In our example $N=12$, for example, the orbits of $R^\times$ on $R$ are $[ [ 0 ], [ 1, 5, 7, 11 ], [ 2, 10 ], [ 3, 9 ], [ 4, 8 ], [ 6 ] ]$. The stabilizer of e.g. $d=3$ is the subgroup of $R^\times$ containing $1$ and $5$. Its orbits on $R$ are $[ [ 0 ], [ 1, 5 ], [ 2, 10 ], [ 3 ], [ 4, 8 ], [ 6 ], [ 7, 11 ], [ 9 ] ]$. Hence we get the pairs $(1,3), (2,3), (4,3), (7,3)$ as the desired coset representatives with $d=3$. (The other values for $c$ are not allowed, as then $gcd(c,d)\neq 1$, which means that $(c,d)\cdot R^\times$ will be too small).