# 3.8 Inverting Matrices Mod n

Finding the inverse of a matrix mod  can be accomplished by the usual methods for inverting a matrix, as long as we apply the rule given in Section 3.3 for dealing with fractions. The basic fact we need is that a square matrix is invertible mod  if and only if its determinant and  are relatively prime.

We treat only small matrices here, since that is all we need for the examples in this book. In this case, the easiest way is to find the inverse of the matrix is to use rational numbers, then change back to numbers mod  It is a general fact that the inverse of an integer matrix can always be written as another integer matrix divided by the determinant of the original matrix. Since we are assuming the determinant and  are relatively prime, we can invert the determinant as in Section 3.3.

For example, in the  case the usual formula is



so we need to find an inverse for 

# Example

Suppose we want to invert  Since  we need the inverse of  mod 11. Since  we can replace  by 5 and obtain



A quick calculation shows that



# Example

Suppose we want the inverse of



The determinant is 2 and the inverse of  in rational numbers is



(For ways to calculate the inverse of a matrix, look at any book on linear algebra.) We can replace 1/2 with 6 mod 11 and obtain



Why do we need the determinant and  to be relatively prime? Suppose  where  is the identity matrix. Then



Therefore,  has an inverse mod  which means that  and  must be relatively prime.