So in my Linear Algebra course I was shown that we cannot directly use row reduction to invert a matrix over a commutative ring in general because the algorithm requires elements to be invertible (which is not always the case in a ring). Inverting a matrix with the formula $A^{-1} = det(A)^{-1}C^T$ is guaranteed to work in every case.
However, it was also shown that in some rings we might still use row reduction in a way. For example, we can treat any matrix over $\mathbb{Z}$ as a matrix over $\mathbb{R}$ and invert it with row reduction – if the computed inverse only has elements in $\mathbb{Z}$, the matrix is invertible.
Knowing that I tried inverting matrices over $\mathbb{Z}/n\mathbb{Z}$ in a similar way. We can compute the inverse of $\begin{pmatrix}1 & 2 \\ 3 & 5\end{pmatrix}$ in $\mathbb{Z}/12\mathbb{Z}$ using the determinant and get $\begin{pmatrix}7 & 2 \\ 3 & 11\end{pmatrix}$. Inverting the same matrix over $\mathbb{R}$ yields $\begin{pmatrix}-5 & 2 \\ 3 & -1\end{pmatrix}$, which is the equivalent matrix modulo $12$, so this seems to work. In another case (matrix in $\mathbb{F}_7$), I was initially disheartened by seeing terms like $\frac{3}{2}$ in the inverse, but then my tutor reminded me that $\frac{3}{2}$ is really just $3\cdot2^{-1}$ which in $\mathbb{F}_7$ is equal to $3\cdot 4 = 12 = 5$.
My question is whether this is guaranteed to work in general. That is, will inverting a matrix in $\mathbb{R}$ and then taking inverses and modulos appropriately be successful exactly if the matrix is invertible in $\mathbb{Z}/n\mathbb{Z}$? It is clear that this is the case if $n$ is prime, because then $\mathbb{Z}/n\mathbb{Z}$ is a field, but what about the other cases? Is it possible that there is such a matrix that is invertible but whose inverse cannot be found by this method? Or conversely, that if such an "inverse" were to be found, it would not actually be an inverse of the matrix?
(As a related question: Are there rings over which matrices can only be inverted by using the determinant? Matrices over polynomials maybe? At least I haven't seen a technique for inverting these matrices with row reduction. But OTOH, I guess most of those matrices are probably not invertible anyway, since it would require the determinant to be of degree $0$).
Best Answer
Inverting the matrix $A$ over the rationals $\mathbb Q$ will fail only if the matrix has determinant $0$ (over $\mathbb Q$). But in that case it also has determinant $0$ mod $n$ for any $n$, so it is not invertible over $\mathbb Z/n\mathbb Z$.
If you do find an inverse $B$ over $\mathbb Q$, and the denominator of some element of $B$ is divisible by some prime $p$ that also divides $n$, then the determinant of $A$ is divisible by $p$, which means $\det(A)$ is not a unit in $\mathbb Z/n\mathbb Z$, and again $A$ is not invertible over $\mathbb Z/n\mathbb Z$.
On the other hand, if all denominators of elements of $B$ are coprime to $n$, then $B$ corresponds to a matrix over $\mathbb Z/n\mathbb Z$ which is an inverse to $A$ there. Namely, if $d$ is the lcm of the denominators, $dB$ is a matrix of integers with $d A B = d I$ (over the integers), and thus $d A B = d I$ over $\mathbb Z/n\mathbb Z$ as well (using the homomorphism of rings $\mathbb Z \to \mathbb Z/n\mathbb Z$).
EDIT: The "standard" row reduction over $\mathbb Z/n \mathbb Z$ doesn't always work: consider the matrix $$ \pmatrix{2 & 3\cr 3 & 5\cr}\ \text{over}\ \mathbb Z/6\mathbb Z$$ This matrix has determinant $1$ and thus is invertible. However, you're stuck right away trying to row reduce, because neither $2$ nor $3$ is invertible mod $6$. What you can do, though, is first add the second row to the first, making the top left matrix element invertible, and proceed from there.
Note that at any stage in the row reduction process, the entries in the next column that don't have leading $1$'s must have gcd coprime to $n$, otherwise the determinant would not be coprime to $n$. By Bezout's identity that gcd is some linear combination of these entries over the integers. Thus by some elementary row operations we can get a pivot entry that is coprime to $n$.