# Inverse of a matrix mod 26

I'm trying to find the inverse of the matrix $\begin{bmatrix} 4 &8 \\ 5 &7 \end{bmatrix} \mod 26$. However the determinant of this matrix is 14 so I cannot use Cramer's rule and each time I try to solve simply by elimination, I end up with non-invertible elements in the resulting matrix.

For example, multiplying the second row by 15: $$\left.\begin{matrix} 4&8 \\ 23&1 \end{matrix}\right| \begin{matrix} 1&0 \\ 0&15 \end{matrix}$$

Then adding the second row the first: $$\left.\begin{matrix} 1&9 \\ 23&1 \end{matrix}\right| \begin{matrix} 1&15 \\ 0&15 \end{matrix}$$ Adding 3 times the first row to the second: $$\left.\begin{matrix} 1&9 \\ 0&2 \end{matrix}\right| \begin{matrix} 1&15 \\ 3&8 \end{matrix}$$

At this point, 2 doesn't have an inverse mod 26 and $2x\equiv9 \pmod{26}$ has no solution. I've tried a number of different combinations of row operations. How can I find the inverse of this matrix?

• If the determinant is not invertible, then the matrix is not invertible. Mar 10 '13 at 2:36

The multiplication formula $$\det(AB)=\det(A)\det(B)$$ is true whenever $A,B$ have elements from a commutative ring. If $A$ is invertible with inverse $A^{-1}$ then $$1=\det(AA^{-1}) = \det(A)\det(A^{-1})$$ so $\det(A)$ is invertible with inverse $\det(A^{-1}).$ So for $A$ to be invertible it is necessary that $\det(A)$ be invertible, which is not the case here. A stronger result is that $A$ is invertible if and only if $\det(A)$ is invertible.
Hint $\rm\: mod\,\ 26\!:\ \left[\begin{array}{c} 4 & 8\\ 5 & 7\end{array}\right]\left[\begin{array}{c}x\\ \rm y\end{array}\right] = \left[\begin{array}{c}0\\ \rm 0\end{array}\right]\$ has solution $\:\left[\begin{array}{c}13\\ \rm 13\end{array}\right]\:$so the matrix is not invertible.
Indeed, if it it were invertible then multiplying by the inverse shows $\ \smash[t]{\rm \left[\begin{array}{c}x\\ \rm y\end{array}\right] = \left[\begin{array}{c}0\\ \rm 0\end{array}\right]}$