Diophantine equation related to coset representatives of $\Gamma_0(N)\backslash SL_2(\mathbb Z)$

Question

I am trying to verify the coset representatives of $\Gamma_0(N)\backslash SL_2(\mathbb Z)$ used in the proof of Proposition 1.43 in Introduction to the Arithmetic Theory of Automorphic Functions by Goro Shimura. If I can show the following, then I will be done.

Let $\alpha=\begin{pmatrix} a & b \\ c & d\end{pmatrix}\in SL_2(\mathbb Z)$. I want to show that there exists $\gamma=\begin{pmatrix}x & k \\ lN & y\end{pmatrix}\in \Gamma_0(N)$ such that the lower right entry of $\gamma\alpha$ is $\gcd(d,N)$. It suffices to show that there exist $l,y\in\mathbb Z$ such that $$lNb+yd=\gcd(N,d)$$ and $\gcd(lN,y)=1$. Since $\gcd(b,d)=1$, we have $\gcd(Nb,d)=\gcd(N,d)$, so the required equation has a solution $(l,y)\in \mathbb{Z}^2$. How can I show that there is a solution $(l,y)\in\mathbb{Z}^2$ with $\gcd(lN,y)=1$?

Answer 1

Let $g=\gcd(d,N)$, $d'=d/g$, $N'=N/g$.

Then $lNb+yd=g$ is equivalent to $lN'b+yd'=1$. This ensures $\gcd(y,lN'b)=1$, so we just need to satisfy the additional constraint $\gcd(y,P)=1$ where $P$ is the product of primes that divide $g$ but not $N'b$.

First find $(l',y')$ such that $l'N'b+y'd'=1$.

If $P=1$, then $(l,y)=(l',y')$ works.

If $P>1$, then there exists $h\in\mathbb{Z}$ with $hN'b\equiv 1\pmod{P}$. Choose $r\in\mathbb{Z}$ coprime to $P$, e.g. $r=1$. Now choose $\lambda\in\mathbb{Z}$ congruent to $h(y'-r)\pmod{P}$. Set $l=l'+\lambda d'$, $y=y'-\lambda N'b$. Thus $lN'b+yd'=1$. Furthermore, $y\equiv y'-hN'b(y'-r)\equiv r\pmod{P}$, which implies that $y$ is coprime to $P$.

Answer 2

Given $gcd(A,C)=1$ and $gcd(A,B)=1$, how to find $u,v$ such that $uA+vB = 1$ and $gcd(v,AC)=1$ ?

Find $u,v$ such that $uA+vB = 1$. The other solutions are $(u-nB)A+(v+nA)B=1$.

Automatically $gcd(v+nA,A) = 1$. So we need $gcd(v+nA,C)=1$. For this let $n \equiv A^{-1}(1-v) \bmod C$. Then $v+nA \equiv 1 \bmod C$ and hence $(u-nB)A+(v+nA)B=1$ is our solution.

In your problem $A = \frac{Nb}{gcd(Nb,d)}, B = \frac{d}{ gcd(Nb,d)}$ and $C$ is the product of primes dividing $gcd(Nb,d)$ and not dividing $A$.