Dear mathoverflow,

Let $ \left( \begin{array}{cc} a & b \newline c & d \end{array} \right) $ be a matrix with $a, b, c, d \in \mathbb{Z}$, $\gcd(a,b,c,d) = 1$ and $ad - bc = \pm N$, with $N > 0$. Does there exist $e, f, g, h, t, u, v, w \in \mathbb{Z}$ such that $$ \left( \begin{array}{cc} N & 0 \newline 0 & 1 \end{array} \right) \cdot \left( \begin{array}{cc} e & f \newline g & h \end{array} \right) = \left( \begin{array}{cc} t & u \newline v & w \end{array} \right) \cdot \left( \begin{array}{cc} a & b \newline c & d \end{array} \right) $$ where $eh - gf = \pm 1$ and $tw - uv = \pm 1$?

In other words, are matrices $ \left( \begin{array}{cc} a & b \newline c & d \end{array} \right) $ and $ \left( \begin{array}{cc} N & 0 \newline 0 & 1 \end{array} \right) $ equivalent with respect to elementary operations?

I would like to have an algorithm to calculate $e,f,g,h,t,u,v$ and $w$.

Thank you.

integerentries? $\endgroup$ – J. M. is not a mathematician May 17 '11 at 12:52