Solving System of Equations modulo a prime 
Consider the equation:
  $$ C \equiv  HMH^{-1}  \pmod{p}, $$
  where $C,M, H$ are, say, $2\times 2$ matrices, and $p$ is an odd prime. The elements of the matrices $C, M$ are integers. The elements of the matrix $H$ are the unknowns (call them $h_{11}, h_{12}, h_{21}, h_{22}$). I am trying to solve this system for the unknowns $h_{11}, h_{12}, h_{21}, h_{22}$.  

Here is my approach:
$$ C \equiv  HMH^{-1}  \pmod{p} $$ 
implies that 
$$CH = HM.$$
This will result in four linear equations in $h_{11}, h_{12}, h_{21}, h_{22}$. That is, we have 
$$W \> h \equiv 0 \pmod{p},$$
where ${h} = transpose(h_{11}, h_{12}, h_{21}, h_{22}). $
Now for the system to have non-trvial solution the matrix $W$ must be singular in $Z_p$ (i.e. $\det(W) \equiv 0 \pmod{p}$). This also would imply that the system
$$W \> { h} \equiv 0 \pmod{p},$$
has at least one free variable, and hence, this system has at least $p-1$ non-trivial solutions.
Is the argument above correct? Any help with this will be highly appreciated.
Thanks in advance!
 A: @user244486,


*

*There is no general formula. 

*Clearly, the associated theory is too complicated for you. 

*Seek the solutions $H\in M_2(F)$ over $F=\mathbb{Z}/3\mathbb{Z}$ when $C=\begin{pmatrix}1&2\\1&1\end{pmatrix},\ M=\begin{pmatrix}a&1\\1&2\end{pmatrix}$. In particular, how to choose $a$ so that there are solutions ?
EDIT. Answer to user244486. It remains to find explicitly all the solutions in $H$ (there are $4$; why ?). Note that there are no eigenvalues of $C,M$ in $F$; indeed they are in an algebraic extension of $F$. Yet $C,M$ are similar over $F$ (this is a theorem !).
A: As far I see you are trying to decide if the matrix $C$ and $M$ are similar. See for example http://en.wikipedia.org/wiki/Matrix_similarity.
A necessary condition for the existence of $H$ is going to be that the so called carateristic polinomial of $C$ and $M$ are the same, i.e. $\det(C) = \det(M)$ and ${\rm trace}(C) = {\rm trace}(M)$. But this conditions are not sufficient. Take for example $C = \left( \begin{array}{cc}
0 & 1  \\
0 & 0 \\ \end{array} \right)$ and $M = \left( \begin{array}{cc}
0 & 0  \\
0 & 0 \\ \end{array} \right)$.  
Turning to your question. I think the condition $\det(W) = 0$ you got is equivalent to $\det(C) = \det(M)$ (but I did not check it). 
If this is so then of course the system  $W.h = 0$ has a non trivial solution but could happen that the nonzero matrix $H$ you got is not invertible hence does not give you a solution of your original question i.e. if $C = H M H^{-1}$.
Summing up what you have to realize is that you are doing linear algebra in a vector space over a finite field. Then you can apply the standard techniques to solve the problem : given $C$ and $M$ does there exists $H$ such that $C = H M H^{-1}$ ?  If you want I can give you the necessary and sufficient conditions for the existence of such $H$. 
