Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 11] PROPERTIES OF THE INTEGERS 279

(a) There are no solutions since 0, 1, 2, and 3 do not satisfy the equation.

(b) There is only one solution among 0, 1 ,...,5 which is 3. Thus the general solution consists of the integers

3 + 6 kwherek∈Z.

(c) There are four solutions, 1, 3, 5, and 7. This shows that a congruence equation of degreencan have more

thannsolutions.

We emphasize that we are not only interested in studying congruence equations in order to find their solutions;
this can always be found by testing. We are mainly interested in developing techniques to help us find such
solutions, and a theory which tells us conditions under which solutions exist and the number of such solutions.
Such a theory holds for linear congruence equations which we investigate below. We will also discuss the Chinese
Remainder Theorem, which is essentially a system of linear congruence equations.

Remark 1:The coefficients of a congruence equation can always be reduced modulomsince anequivalent
equation, that is, an equation with the same solutions, would result. For example, the following are equivalent
equations since the coefficients are congruent modulom=6:

15 x^2 + 28 x+ 14 ≡ 0 (mod 6), 3 x^2 + 4 x+ 2 ≡ 0 (mod 6), 3 x^2 − 2 x+ 2 ≡ 0 (mod 6),

Usually we choose coefficients between 0 andm−1 or between−m/2 andm/ 2

Remark 2:Since we are really looking for solutions of (11.2) among the residue classes modulomrather than
among the integers, we may view (11.2) as an equation over the integers modulom, rather than an equation
overZ, the integers. In this context, the number of solutions of (11.2) is simply the number of solutions inZm.

Linear Congruence Equation: ax≡1 (modm)

First we consider the special linear congruence equation

ax≡ 1 (modm) (11.3)

wherea≡ 0 (modm). The complete story of this equation is given in the following theorem (proved in
Problem 11.57).

Theorem 11.26: Ifaandmare relatively prime, thenax≡1 (modm) has a unique solution; otherwise it has
no solution.

EXAMPLE 11.16

(a) Consider the congruence equation 6x≡1 (mod 33). Since gcd( 6 , 33 )=3, this equation has no solution.

(b) Consider the congruence equation 7x≡1 (mod 9). Since gcd( 7 , 9 )=1, the equation has a unique solution.

Testing the numbers 0, 1, ..., 8, we find that

7 ( 4 )= 28 ≡ 1 (mod 9)

Thusx=4 is our unique solution. (The general solution is 4+ 9 kfork∈Z.)

Suppose a solution of (11.3) does exist, that is, suppose gcd(a, m)=1. Furthermore, suppose the modulus
mis large. Then the Euclidean algorithm can be used to find a solution of (11.3). Specifically, we use the
Euclidean algorithm to findx 0 andy 0 such that

ax 0 +my 0 = 1

From this it follows thatax 0 ≡1 (modm); that is,x 0 is a solution to (11.3).