# How does this argument to count the cusps of $Γ_0 (N)$ work?

This question regards counting the cusps of $Γ_0 (N)$.

I’ve been trying for a while to understand the following argument to count the cusps of $Γ_0(N)$ given in A First Course in Modular Forms by Diamond & Shurman, so here is the full argument for reference (you can find it in chapter 3.8. page 103):

To count the cusps of $Γ_0 (N)$ recall from Proposition 3.8.3 that for this group, vectors $\begin{bmatrix}a \\ c\end{bmatrix}$ and $\begin{bmatrix}a' \\ c'\end{bmatrix}$ with $\gcd(a,c) = \gcd(a',c') = 1$ represent the same cusp when $\begin{bmatrix}ya' \\ c'\end{bmatrix} \equiv \begin{bmatrix}a +jc \\ c\end{bmatrix}\bmod{N}$ for some $j$ and $y$ with $\gcd(y,N)$. The bottom condition, $c' \equiv yc \mod{N}$ for some such $y$, is equivalent to $\gcd(c',N) = \gcd(c,N)$, in wich case letting $d = \gcd(c,N)$ and letting $y_0 ∈ ℤ$ satisfy $y_0 \equiv c'c^{-1} \bmod{N}$ makes the condition equivalent to $y \equiv y_0 + iN/d \bmod{N}$ for some $i$ (confirming the calculatons in the paragraph is Exercise 3.8.4.). For any divisor $d$ of $N$, pick one value $c$ modulo $N$ such that $\gcd(c,n) = d$. Then any cusp of $Γ_0(N)$ represented by some Vector $\begin{bmatrix}a' \\ c'\end{bmatrix}$ with $\gcd(c',N) = d$ is also represented by $\begin{bmatrix}a \\ c\end{bmatrix}$ whenever $(y_0 + iN/d)a' \equiv a+jc \bmod{N}$ for some $i$ and $j$, or $a \equiv y_0a' \bmod \gcd(c,N,a'N/d)$, or $a \equiv y_0 a' \bmod{\gcd(d,N/d)}$. Also, $a$ is relatively prime to $d$ since $\gcd(a,d) \mid \gcd(a,c) = 1$, so $a$ is relatively prime to $\gcd(d,N/d)$. Thus for each divisor $d$ of $N$ there are $ϕ(\gcd(d,N/d))$ cusps, and the number of cusps of $\Gamma_0 (N)$ is therefore $\sum_{d \mid N} ϕ(\gcd(d,N/d))$.

First of all I have a problem with this sentence:

Then any cusp of $Γ_0(N)$ represented by some Vector $\begin{bmatrix}a' \\ c'\end{bmatrix}$ with $\gcd(c',N) = d$ is also represented by $\begin{bmatrix}a \\ c\end{bmatrix}$ whenever $(y_0 + iN/d)a' \equiv a+jc \bmod{N}$ for some $i$ and $j$, or $a \equiv y_0a' \bmod \gcd(c,N,a'N/d)$, …

As I understand it, $y_0 + i N/d$ doesn’t need to be a number relatively prime to $N$, so this can’t be an equivalence. Therefore, to me the argument only shows that two vectors which represent the same cusp and have relatively prime components have the same upper component modulo $\gcd(d,N/d)$ and this component is relatively prime to $\gcd(d,N/d)$. But this doesn’t mean, that any element less than and relatively prime to $\gcd(d,N/d)$ can be interpreted as the first component of vector representing a cusp. Nor does it mean that any two different such elements give rise to different cusps.

Can anyone shed some light on how to understand this argument?

This queston might just be a little too localized for any of these sites while it hardly counts as a research question, so it might better be fitting math.stackexchange. I just get the impression that I have better chances here of getting an answer, so I’ll just give it a shot. I do not know whether such questions are tolerated here.

I also feel unsure about the tags. I now tagged the question as combinatorics and number-theory, since it’s about counting things using divisibility arguments.

Theorem. The cusps $\frac{u_1}{v_1},\frac{u_2}{v_2}\in\mathbb{Q}\cup\{\infty\}$, given in lowest terms, are equivalent under $\Gamma_0(q)$ if and only if there exists $v\mid q$ such that $(q,v_1)=(q,v_2)=v$ and $u_1v_1\equiv u_2v_2\pmod{(q,v^2)}$.
Proof. Fixing arbitrary elements $\begin{pmatrix}u_1&\overline v_1 \cr v_1&\overline u_1\end{pmatrix}, \begin{pmatrix}u_2&\overline v_2 \cr v_2&\overline u_2\end{pmatrix}\in\mathrm{SL}_2(\mathbb{Z})$ we need to examine the statement $$\exists \gamma\in\Gamma_0(q) : \begin{pmatrix}u_1&\overline v_1 \cr v_1&\overline u_1\end{pmatrix}\infty =\gamma\begin{pmatrix}u_2&\overline v_2 \cr v_2&\overline u_2\end{pmatrix}\infty.$$ This is clearly \begin{align*} &\Longleftrightarrow \exists \gamma\in\Gamma_0(q) : \exists n\in\mathbb{Z} : \begin{pmatrix}1&n \cr 0&1\end{pmatrix}= \begin{pmatrix}u_1&\overline v_1 \cr v_1&\overline u_1\end{pmatrix}^{-1} \gamma\begin{pmatrix}u_2&\overline v_2 \cr v_2&\overline u_2\end{pmatrix} \cr &\Longleftrightarrow \exists n\in\mathbb{Z} : \begin{pmatrix}u_1&\overline v_1 \cr v_1&\overline u_1\end{pmatrix} \begin{pmatrix}1&n \cr 0&1\end{pmatrix} \begin{pmatrix}u_2&\overline v_2 \cr v_2&\overline u_2\end{pmatrix}^{-1}\in\Gamma_0(q) \cr &\Longleftrightarrow \exists n\in\mathbb{Z} : \begin{pmatrix}u_1&\overline v_1+nu_1 \cr v_1&\overline u_1+nv_1\end{pmatrix} \begin{pmatrix}\overline u_2&-\overline v_2 \cr -v_2&u_2\end{pmatrix}\in\Gamma_0(q) \cr &\Longleftrightarrow \exists n\in\mathbb{Z} : \overline u_2 v_1-\overline u_1 v_2-nv_1v_2\equiv 0\pmod{q} \cr &\Longleftrightarrow \exists m,n\in\mathbb{Z} : \overline u_2 v_1-\overline u_1 v_2=qm+nv_1v_2 \cr &\Longleftrightarrow \overline u_2 v_1\equiv\overline u_1 v_2\pmod{(q,v_1v_2)}. \end{align*} Let us examine the last condition. Observe that by $(\overline u_1,v_1)=(\overline u_2,v_2)=1$ the congruence forces $(q,v_1)\mid v_2$ and $(q,v_2)\mid v_1$, i.e. $(q,v_1)=(q,v_2)$. Denoting this common value by $v$ and writing $q=vw$, the congruence becomes $\overline u_2 v_1/v\equiv\overline u_1 v_2/v\pmod{(w,v_1v_2/v)}$. Note that $(v_1/v,q/v)=(v_1,q)/v=1$ and $(v_2/v,q/v)=(v_2,q)/v=1$, i.e. both $v_1/v$ and $v_2/v$ are coprime to $w$. In particular, $v_1v_2/v=v(v_1/v)(v_2/v)$ shows that $(w,v_1v_2/v)=(w,v)$ and the congruence further simplifies to $\overline u_2 v_1/v\equiv\overline u_1 v_2/v\pmod{(w,v)}$. Note also that $u_1\overline u_1$ and $u_2\overline u_2$ are $\equiv 1\pmod{v}$, hence the congruence is equivalent to $u_1 v_1/v\equiv u_2 v_2/v\pmod{(w,v)}$. Multiplying this by $v$ we obtain the congruence in the theorem.
Corollary. The number of inequivalent cusps of $\Gamma_0(q)$ equals $\sum_{q=vw}\varphi((v,w))$.
Proof. For any decomposition $q=vw$ and any reduced residue class $u'\mod(v,w)$ we pick some $u\in\mathbb{Z}$ such that $(u,v)=1$ and $u\equiv u'\pmod{(v,w)}$. This exists by the Chinese remainder theorem, e.g. we can take $u\in\mathbb{Z}$ such that $u\equiv 1\pmod{p}$ for any prime $p\mid v$ with $p\nmid w$ and also $u\equiv u'\pmod{(v,w)}$. By the above Theorem (or its proof), the resulting rational numbers $\frac{u}{v}$ represent the $\Gamma_0(q)$-orbits of $\mathbb{Q}\cup\{\infty\}$, and their number equals $\sum_{q=vw}\varphi((v,w))$.