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}$$