List of Propositions - Introduction to Cryptography with Java Applets - page 352

a. a + c b + c (mod m )

b. a c b c (mod m )

c. ac bc (mod m ).

Proposition 20. Let a , b , and c be integers, and let m be a positive integer. Suppose
a b (mod m ), and c d (mod m ). Then
a. a + c b + d (mod m )

b. a c b d (mod m )

c. ac bd (mod m ).

Proposition 21. Let a , b , and c be integers, and m a positive integer. Let d = ( c , m ),
and suppose ac bc (mod m ). Then a b (mod m / d ).

Proposition 22. Suppose ax b (mod m ), where a , b , and m are all positive integers.
Let d = ( a , m ). If d b , the congruence has no solution for x . If d | b , then there are exactly
d incongruent solutions modulo m , given by x = x 0 + tm / d , where x 0 is a particular solution
to the linear diophantine equation ax + my = b , and t = 0, 1, . . . , d 1.

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

Proposition 24. Suppose two n k matrices A and B are such that A B (mod m ).
Then AC BC (mod m ) for any k p matrix C , and DA DB (mod m ) for any q n matrix
D .

Proposition 25. Suppose integers a 1 , a 2 , ..., a n are pairwise relatively prime. Then
( a 1 a 2 ... a n )| c if and only if a 1 | c , a 2 | c , ..., a n | c .

Proposition 26. Let a b (mod m 1 ), a b (mod m 2 ), . . . , a b (mod m n ) where a 1 ,
a 2 , ..., a n are pairwise relatively prime. Then we have a b (mod m 1 m 2 ... m n ).

Proposition 27. (The Chinese Remainder Theorem.)

Suppose m 1 , m 2 , . . . , m n

are pairwise relatively prime. Then the system of congruences
x a 1 (mod m 1 )
x a 3 (mod m 3 )
...

x a n (mod m n )
has a unique solution modulo M = m 1 m 2 ... m n , namely,
x a 1 M 1 y 1 + a 2 M 2 y 2 + . . . + a n M n y n (mod M )