Linear Diophantine Equations and Linear Congruences - Introduction to Cryptography with Java Applets - page 96

We now have enough artillery in our arsenal to solve linear congruences. A linear con-
gruence in one variable is of the form ax b (mod m ) where x is unknown. The following
are examples of such congruences:
a.

9 x 1 (mod 45)

b. 21 z 9 (mod 30)

Some of these congruences have solutions, while others do not. For example, the con-
gruence (b) has all of the following solutions for z :

z 9 (mod 30), since 21 9 = 189 9 (mod 30)
z 19 (mod 30), since 21 19 = 399 9 (mod 30)
z 29 (mod 30), since 21 29 = 609 9 (mod 30)

However, the congruence (a) has no solutions for x . Why? The following tells us when
solutions exist, and how to find them.

PROPOSITION 22. Suppose ax b (mod m ), where b is an integer, and a and m are
nonzero 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.

Proof. Proposition 7 says that the linear congruence ax b (mod m ) is equivalent to the
linear diophantine equation ax mz = b , or ax + my = b where y = z . The integer x is a
solution of ax b (mod m ) iff ∃ an integer y such that ax + my = b . By proposition 16 we
have no integer solutions to this equation if d b , but when d | b , we have infinitely many
solutions given by

x = x 0 + mt / d , y = y 0 + at / d , where x = x 0 , y = y 0 is a particular solution.
These values for x are then solutions to ax b (mod m ). To determine which solutions
are congruent modulo m , suppose
x 0 + mr / d x 0 + ms / d where r and s are integers.
Subtract x 0 from both sides to get
( m / d ) r ( m / d ) s (mod m )
and note that ( m , m / d ) = m / d since ( m / d )| m . We then use proposition 21 to see that

r s (mod d ).
This says that two solutions x 0 + mr / d and x 0 + ms / d are congruent modulo m exactly when
r and s are congruent modulo d . Thus, the complete set of incongruent solutions x = x 0 + mt / d
is obtained as t spans the integers 0, 1, . . . , d 1.

Just stating proposition 22 sounds like a mouthful, but using it to solve linear congruences
is actually easy, as we'll see in the following examples. Note that for linear congruences,
as with linear diophantine equations, we concern ourselves only with congruences where all