Systems of Linear Congruences—Multiple Moduli - Introduction to Cryptography with Java Applets - page 160

CHAPTER 8

Systems of Linear Congruences—
Multiple Moduli

Now we proceed with the next type of linear systems of congruences. These systems
involve a single variable with multiple moduli, as in the following example:

x 3 (mod 4)

x 0 (mod 5) (*)

x 0 (mod 7)

x 8 (mod 9).

which solve all four of the congruences in (*). We can go
about finding solutions as follows: first, rewrite the first congruence as an equality

We wish to find all integers x

x = 4 t + 3

where is an integer (proposition 17 allows this). Insert this expression into the second

congruence to get

x

4 t + 3 0 (mod 5),

then solve for t to get

t 3 (mod 5).

We can now rewrite the previous as an equation

t = 5 u + 3

which we can then substitute for x in the next congruence, since

x = 4 t + 3 = 4(5 u + 3) + 3 = 20 u + 15.

Doing this, we see that

20 u + 15 6 u + 1 0 (mod 7)