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

holds for matrices representing congruences, provided the scalar multiple is relatively prime
to the modulus. Lastly, it is clear from proposition 20 that operation 3 is still valid for matri-
ces when they are used to represent congruences. Proposition 20 says we can add congru-
ent items to both sides of a congruence without changing the congruence.

Thus, we can solve the previous system (*) using elementary row operations on the aug-
mented matrix. We will attempt to produce an upper triangular matrix, then use back sub-
stitution to obtain values for the variables. When this is done using matrices defined over
the real numbers it is called Gaussian elimination; we may as well call it that in this setting,
too.

5322
3461
2114

The augmented matrix A | B .

5322
6152
2114

Multiply second row by 2; all operations are done modulo 7 and the least nonnegative
residue is retained.

5322
0524
2114

Subtract 3 times third row from second row.

5322
0524
5663

Multiply third row by 6.

5322
0524
0341

Subtract first row from third row.

5322
0524
0524

Multiply third row by 4.

5322
0524
0000