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

Subtract second row from third row. Here we obtain a row of all zeros (mod 7), so we can-
not get a unique solution in this case. (Here, of course, we take a unique solution to mean
that all other solutions are congruent to it).

1266
0165
0000

Multiply both the first and second rows by 3, an inverse of 5 modulo 7. This gives the fol-
lowing solutions for the system:
y 6 z + 5 z + 5 (mod 7), and
x 2 y 6 z + 6 5 y + z + 6 5( z + 5) + z + 6 6 z + 25 + 6 6 z + 3 (mod 7).

to range from 0 through 6, we can list all of the incongruent solutions to
this system. They are presented in Table 6.2, and you are asked to recompute each solution
and to verify each of them.
The preceding example teaches us an important lesson: that systems of congruences may
have multiple solutions due to linear dependence, as it is in linear algebra. Of course, when
dealing with congruences, we have finitely many incongruent solutions, rather than infi-
nitely many solutions as when dealing with systems of equations defined over the real num-
bers.

If we allow z

6.2

MODULAR MATRIX INVERSES
Later on it will be useful for us to be able to obtain the inverse of a square mm matrix A
modulo n . That is, we will wish to find the matrix M such that MA AM I (mod n ),
where I is the mm identity matrix.

100 ··· 0

010 ··· 0

0
··· ··· ··· ··· ···
00001

001 ···

Of course, an inverse modulo n of a matrix A may not exist, but when it does, we denote

it as , and using

Gauss-Jordan elimination with elementary row operations. We illustrate how this will be
done with an example; we will attempt to find an inverse modulo 5 of the 2

A . We should be able to find it by forming the augmented matrix A | I

2 matrix A ,

which is

14
22

TABLE 6.2

x3210654
y5601234
z 0123456