I have a question which is fairly elementary, but first I must provide relevant context. Without it, my question would seem rather arbitrary and scarcely interesting. Note also that my question can be answered without reading what follows. 


Let $j(\omega)$ be the modular invariant, $\Gamma$ be the modular group and $H$ the upper half-plane. Define $\gamma\_2(\omega)=\sqrt[3]{j(\omega)}$ using the cube root which is real on the imaginary axis. 


Let $\tau\in H$ satisfy
\begin{equation}
 A\tau^2+B\tau+C=0,\ (A,B,C)=1.
\end{equation}


By Class field theory the value $j(\tau)$ is an algebraic integer of degree exactly $h(D)$, where $D=B^2-4AC$. Since $\gamma\_2(\tau)^3-j(\tau)=0$ one would expect the degree of $\gamma\_2(\tau)$ to be $3h(D)$. But it turns out that, if $(A,3)=1$ and $3\mid B$, the degree of $\gamma\_2(\tau)$ is also $h(D)$.


Now I indicate how this result can be proved.


Set $\varepsilon=e^{-\frac{2\pi i}{3}}$. It can be shown that for $\bigl( \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} \bigr)\in\Gamma$ we have


\begin{equation}
\gamma\_2{\left(\frac{a\omega+b}{c\omega+d}\right)}=\varepsilon^{ab-ac+cd-a^2cd}\gamma\_2(\omega).
\end{equation}
This implies that $\gamma\_2(\omega)=\gamma\_2(\tau)$ if and only if $A\omega=\tau$, with $A=\bigl( \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} \bigr)\in\Gamma$ satisfying $ab-ac+cd-a^2cd \equiv 0 \ (\textrm{mod}\ 3)$, except when $\omega \equiv e^{-\frac{2\pi i}{3}} \ (\textrm{mod}\ \Gamma)$, in which case $\gamma\_2(\omega)=0$.


Next define
\begin{equation}
S(n,3)=\bigg\lbrace\begin{pmatrix}
 r & s\\
 0 & t
\end{pmatrix}:rt=n,r>0,(r,s,t)=1,3\mid s,0\leq s <3t \bigg\rbrace.
\end{equation}
Let $\omega$ be in the upper half-plane $H$. Consider the polynomial
\begin{equation}
\phi\_{n,\omega}(x)=\prod\_{M\in S(n,3)}\left(x-\gamma\_2(M\omega)\gamma\_2(\omega)^{-n} \right).
\end{equation}
It takes some work to show that the coefficients of this polynomial are invariant under $\Gamma$, and therefore rational functions in $j(\omega)$. After additional work we conclude that they are in fact polynomials with integral coefficients. In this way we get a polynomial $\Phi\_n(x,y)\in \mathbb Z[x,y]$ such that $\Phi\_n(x,j(\omega))=\phi\_{n,\omega}(x)$. Applying a suitable substitution we obtain another polynomial $\Psi\_n(x,y)\in \mathbb Z[x,y]$ satisfying for all $0\neq z \in \mathbb C$


* $\Psi\_n(z,z)=0$ is equivalent to $z=\gamma\_2(\omega)=\gamma\_2(M\omega)$ for some $M\in S(n,3)$ and $\omega\in H$.


Thus if $0\neq z \in \mathbb C$ is a root of $\Psi\_n(x,x)=0$ then we must have for some $\omega$ and $M=\bigl(\begin{smallmatrix} r & s \\ 0 & t \end{smallmatrix} \bigr)\in S(n,3)$
\begin{equation}
z=\gamma\_2(\omega)=\gamma\_2(M\omega)
\end{equation}
and consequently by the fourth paragraph
\begin{equation}
\frac{a\omega+b}{c\omega+d}=\frac{r\omega+s}{t}
\end{equation}
where $a,b,c,d$ are integers such that $ad-bc=1$ and $ab-ac+cd-a^2cd \equiv 0 \ (\textrm{mod}\ 3)$. Hence $\omega$ is a root of a quadratic equation with integral coefficients, and if $n$ is suitably chosen, then the middle coefficient will be divisible by $3$. Conversely if we can find $\bigl( \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} \bigr)$ and 
$\bigl(\begin{smallmatrix} r & s \\ 0 & t \end{smallmatrix} \bigr) $ with these properties, $\gamma\_2(\omega)$ will be a root of $\Psi\_n(x,x)=0$


On the other hand the roots of the equation
\begin{equation}
 x^3-j(\omega)=0
\end{equation}
are 
\begin{equation}
 \gamma\_2(\omega),\ e^{-2\pi i/3}\gamma\_2(\omega)=\gamma\_2(\omega+1),\ e^{2\pi i/3}\gamma\_2(\omega)=\gamma\_2(\omega-1)
\end{equation}


If we could guarantee that the only common root of $\Psi\_n(x,x)$ and $x^3-j(\omega)$ is $\gamma\_2(\omega)$, then we would know that $\gamma\_2(\omega)$ and $j(\omega)$ had the same degree. But if $A$ is not divisible by $3$, $B$ is divisible by $3$ and
\begin{equation}
 A\omega^2+B\omega+C=0,\ (A,B,C)=1.
\end{equation}
then it is easy to see that the numbers $\omega + 1$ and $\omega -1$ satisfy quadratic equations whose middle coefficients are not divisible by $3$. Therefore $\gamma\_2(\omega)$ is the only common root and we are done.


**Finally, my question is this: given $\omega\in H$ such that $\omega^2+3\omega+\frac{9-D}{4}=0$ where $D\equiv 5 \ (\textrm{mod} \ 8)$ and $D<0$ is not divisible by 3, how can I find $n\equiv -1 \ (\textrm{mod}\ 3)$ and $M\in S(n,3)$ such that 
$$A\omega=M\omega$$ holds for some $A=\bigl( \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} \bigr)\in\Gamma$ satisfying $ab-ac+cd-a^2cd \equiv 0 \ (\textrm{mod}\ 3)$?**



The degree of the cube root of the $j$-invariant
Let $N=\frac {9-D}{4}$ and let $\bar\omega$ be the complex conjugate of $\omega$. In particular $\omega+\bar\omega = -3$ and $\omega\bar\omega=N$.


For every $A=\bigl(\begin{smallmatrix}a & b\\c&d\end{smallmatrix}\bigr)\in\Gamma$ we have that $ad=bc+1$, so $$A\omega = \frac{(a\omega +b)(c\bar\omega+d)}{(c\omega+d)(c\bar\omega+d)}=\frac{ac(\omega\bar\omega) +\omega + bc(\omega+\bar\omega)+bd}{c^2(\omega\bar\omega) +cd(\omega+\bar\omega)+d^2}=M\omega$$
with $M=\bigl(\begin{smallmatrix}r & s\\0&t\end{smallmatrix}\bigr)$ and $$\begin{aligned}r&=1 ,\\s&=bd-3bc+Nac , \\ t&=d^2-3cd+Nc^2.\end{aligned}$$ 


Of course we have $r>0$, $gcd(r,s,t)=1$ and $n=t$. We now show how to choose appropriate $a,b,c,d$ to fulfil all the other requirements. We will choose $a,b,c,d> 0$ to be positive integers. 


Since the discriminant $\Delta=(-3)^2 - 4 N$ is negative, we have that $t>0$. Since $s=\frac b d t + \frac c d N$, we also have $s>0$.


If $N\equiv 1\pmod 3$ we choose $a\equiv -d\not\equiv 0\pmod 3$ and $b\equiv c\not\equiv 0\pmod 3$. 
If $N\equiv -1\pmod 3$, we choose $a\equiv -d\equiv 0\pmod 3$ and $b\equiv c\not\equiv 0\pmod 3$. 


In this way, $n=t\equiv -1\pmod 3$, $s\equiv 0\pmod 3$ and $ab-ac+cd+a^2cd\equiv 0\pmod 3$.


Finally, the requirement $s=\frac b d t +\frac c d N< 3t$ is satisfied whenever $d$ is chosen sufficiently large, compared to $b,c,N$, subject to $ad=bc+1$ and all the conditions above.


Here is a choice of parameters that works, because $N$ is an integer and $N\geq 2$:


* if $N\equiv 1\pmod 3$, choose $A= \bigl(\begin{smallmatrix}1 & 1\\1&2\end{smallmatrix}\bigr)$ and $M= \bigl(\begin{smallmatrix}1 & N-1\\0&N-2\end{smallmatrix}\bigr)$;
* if $N\equiv -1\pmod 3$, choose $A= \bigl(\begin{smallmatrix}3 & 2\\4&3\end{smallmatrix}\bigr)$ and $M= \bigl(\begin{smallmatrix}1 & 12N-18\\0&16N-27\end{smallmatrix}\bigr)$.


A cool thing is that we can choose $A$ almost independently of $\omega$!


