Determine a matrix given two other matrices 
Define the following matrices $C,P\in M_2(\mathbb{Z}_{26})$:
  $$
C=\begin{pmatrix}22&13\\10&2\end{pmatrix},\quad P=\begin{pmatrix}6&21\\8&4\end{pmatrix}.
$$
  Find an invertible matrix $A\in M_2(\mathbb{Z}_{26})$ such that $C=AP$.

My first attempt is to obtain $A$ as $CP^{-1}$. Unfortunately, $\det{P}=12$ and $\gcd(\det{P},26) = 2$. Hence $P$ is not invertible and this approach doesn't work. 
Yet, if $C=AP$ is solvable with an invertible $A$ over $\mathbb Z_{26}$, it must also be solvable with an invertible $A$ over $\mathbb Z_{13}$. So, my second attempt is to solve the equation
$$
\tilde{C}=\tilde{A}\tilde{P}\tag{1}
$$
over $\mathbb Z_{13}$, where
\begin{align}
\tilde{C} &= \begin{pmatrix}22&13\\10&2\end{pmatrix}
= \begin{pmatrix}9&0\\10&2\end{pmatrix},\\
\tilde{P} &= \begin{pmatrix}6&21\\8&4\end{pmatrix}
=\begin{pmatrix}6&8\\8&4\end{pmatrix},
\end{align}
and then set
$$A = \tilde{A} + 13A_1\tag{2}$$
for some $A_1\in M_2(\mathbb Z_{26})$ whose entries are either zero or one. (We abuse the notation $\tilde{A}$ here to mean also a matrix with entries in $\mathbb Z_{26}$.) Since $\det\tilde{P} = 12 = -1$ in $\mathbb Z_{13}$, we have
$$
\tilde{P}^{-1} = -\begin{pmatrix}4&-8\\-8&6\end{pmatrix}
=\begin{pmatrix}9&8\\8&7\end{pmatrix}
$$
and hence
$$
\tilde{A} =\tilde{C}\tilde{P}^{-1}
=\begin{pmatrix}9&0\\10&2\end{pmatrix}\begin{pmatrix}9&8\\8&7\end{pmatrix}
=\begin{pmatrix}3&7\\2&3\end{pmatrix}.
$$
Now I'm struggling on finding the correct choice for $A_1$. There are $2^4=16$ different choices and I feel like checking the determinant for all these matrices is incredibly time consuming. Is there a quicker way to do this?
We want the new $A$ to satisfy $\gcd(\det{A},26)=1$ and therefore $\gcd(\det{A},2)=1$ so that we can find $A^{-1}$.

I would rewrite this as $P^TA^T=C^T$ so it is more consistent with the way we normally view Gaussian elimination. Then
$$\begin{align}\begin{bmatrix}6&8&22&10\\21&4&13&2\end{bmatrix} & \xrightarrow{R_1\leftrightarrow R_2}\begin{bmatrix}21&4&13&2\\6&8&22&10\end{bmatrix}\\
 & \xrightarrow{R_1\times5}\begin{bmatrix}1&20&13&10\\6&8&22&10\end{bmatrix}\\
 & \xrightarrow{R_2+20R_1}\begin{bmatrix}1&20&13&10\\0&18&22&2\end{bmatrix}\\
 & \xrightarrow{R_2\times3}\begin{bmatrix}1&20&13&10\\0&2&14&6\end{bmatrix}\\
 & \xrightarrow{R_1+16R_2}\begin{bmatrix}1&0&3&2\\0&2&14&6\end{bmatrix}\end{align}$$
So now we can read the solution as $A_{11}\equiv3\pmod{26}$, $A_{21}\equiv2\pmod{26}$, $2A_{12}\equiv14\pmod{26}$, and $2A_{22}\equiv6\pmod{26}$. So one of the $4$ possible solutions is
$$A=\begin{bmatrix}3&7\\2&3\end{bmatrix}$$
