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

for matrices when used for congruences. Recall from linear algebra the three basic row
operations that are permitted on matrices; we will modify these rules slightly:
1.

Any two rows may be exchanged.

2. Any row may be multiplied by a nonzero scalar.

3. A multiple of any row may be added to another row.

We redefine the three elementary row operations for matrices used to represent a system
of congruences:

Definition
The three elementary row operations for matrices modulo n are:

1. Any two rows may be exchanged.
2. Any row may be multiplied by an integer scalar relatively prime to the modulus.
(Call this a multiple of a row.)
3. A multiple of a row may be added to another row.

We will show now that when the elementary operations are defined this way, they do not
affect the solutions to a system of congruences.

PROPOSITION 23. When matrices are used to represent a system of linear congru-
ences, the three elementary row operations for matrices do not affect the solution(s) of the
corresponding system of congruences modulo n .

Proof. Operation 1 clearly still holds if the matrices are representing congruences, for
switching the order of the congruences in a system does not affect the solution. If scalars
are always understood to be integers, then multiplying both sides of a congruence by a scalar
that is relatively prime to the modulus will not alter the solution. To see this, consider the
congruence

acx + bcy dc (mod n ) ($)
where c is relatively prime to n . Suppose x = x , y = y is a solution to this congruence; that
is,

acx

+ bcy dc (mod n ).

Then we have

ax + by d (mod n )
by Proposition 21, and so x = x , y = y is also a solution to the congruence
ax + by d (mod n ).

($$)

Clearly, the reverse is also true: If x = x 0 , y = y 0 is a solution to ($$), then it is also a solu-
tion to ($). So, the solutions to ($) and ($$) are identical when ( c , n ) = 1, so operation 2 also