Suppose I have two elements A, B of the modular group (i.e. 2x2 integer matrices with unit determinant) that have the same trace. I would like to know when these two matrices are conjugates of each other in the modular group, i.e. when I can find a modular matrix P such that $A = P.B.P^{-1}$.
I understand that having equal trace is not enough. So what other conditions do I have to impose on A and B to find the desired matrix P (from the modular group). And if it exists, is there an algorithm that would produce such P from A and B (i.e. one of them, as there are infinitely many such matrices in that case)?
You can solve the equation $$AP=PB$$ for an arbitrary integer matrix $P$. If $A$ and $B$ are conjugate, the general solution will be $P=xP_1+yP_2$ where $x$, $y\in\Bbb Z$. The determinant of $P$ will be a quadratic form in $x$ and $y$ so you have to find if and where it represents $1$. In effect you have to solve a generalized Pell equation.