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?
> 
> 
> 




---


I feel very unsure about whether this is the right place to ask.
I’ve already asked similar questions on math.stackexchange:


* [In $ℤ/Nℤ$, which units are succesors to zero divisors?](https://math.stackexchange.com/questions/407826/in-n-which-units-are-successors-to-zero-divisors), and
* [Which assignment defines a bijection here? And what is its inverse? And why?](https://math.stackexchange.com/questions/384516/which-assignment-defines-a-bijection-here-and-what-is-its-inverse-and-why)


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.



How does this argument to count the cusps of $Γ_0 (N)$ work?
I don't have time to analyze the proof in Diamond-Shurman, but for what it is worth, here is my own treatment as I teach it to my students.


**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'\bmod(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))$.


