Systems of Linear Congruences—Single Modulus - Introduction to Cryptography with Java Applets - page 129

Specifically, we are looking for a matrix A such that

AA AA I (mod 5).

We begin by joining the matrix A with the 2 2 identity matrix.

1410
2201

The augmented matrix A | I .

1410
0431

Subtract twice the first row from the second row. All operations are done modulo 5, and the
least nonnegative residue is retained.

1034
0431

Subtract the second row from the first row.

1034
0124

Multiply the second row by 4, an inverse of 4 modulo 5. Now, we have A , an inverse of A
modulo 5; it is the matrix

34
24

To verify that this is an inverse of A modulo 5, take the product AA (you could also take
AA ), and verify that you get the 2 2 identity matrix. We do this here:

≡

14
22

34
24

10
01

(mod 5)

Now that we have discussed finding inverses, we discuss how they may be used. When
an inverse modulo

n A

of a square matrix exists, it is quite useful in solving linear systems

of congruences, for if

AX B n

(mod ),

A A n

then by finding , an inverse of modulo , we can find the solutions by multiplying both

A

sides of the congruence by :

AAX AB (mod n ).

The left-hand side of the above simplifies to

AAX IX X (mod n ),

which then yields

X AB (mod n ).