Diophantine equation related to coset representatives of $\Gamma_0(N)\backslash SL_2(\mathbb Z)$ 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$?
 A: 
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$.
A: 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$.
