Number theory 4

CONGRUENCE EQUATIONS
A polynomial congruence equation or, simply, a congruence equation (in one unknown x) is an equation of
the form
anxn + an?1xn?1 + . . . + a1x + a0 ? 0 (mod m) (11.2)
Such an equation is said to be of degree n if a ? 0 (mod m).
Suppose s ? t (mod m). Then s is a solution of (11.2) if and only if t is a solution of (11.2). Thus the
number of solutions of (11.2) is defined to be the number of incongruent solutions or, equivalently, the number
of solutions in the set
{0, 1, 2, . . . , m ? 1}
Of course, these solutions can always be found by testing, that is, by substituting each of the m numbers into
(11.2) to see if it does indeed satisfy the equation.
The complete set of solutions of (11.2) is a maximum set of incongruent solutions whereas the general
solution of (11.2) is the set of all integral solutions of (11.2). The general solution of (11.2) can be found by
adding all the multiples of the modulus m to any complete set of solutions.
EXAMPLE 11.15 Consider the equations:
(a) x2 + x + 1 ? 0 (mod 4), (b) x2 + 3 ? 0 (mod 6), (c) x2 ? 1 ? 0 (mod 8)
Here we find the solutions by testing.
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 + 6k where k ? Z.
(c) There are four solutions, 1, 3, 5, and 7. This shows that a congruence equation of degree n can have more
than n solutions.
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 modulo m since an equivalent
equation, that is, an equation with the same solutions, would result. For example, the following are equivalent
equations since the coefficients are congruent modulo m = 6:
15x2 + 28x + 14 ? 0 (mod 6), 3x2 + 4x + 2 ? 0 (mod 6), 3x2 ? 2x + 2 ? 0 (mod 6),
Usually we choose coefficients between 0 and m ? 1 or between ?m/2 and m/2
Remark 2: Since we are really looking for solutions of (11.2) among the residue classes modulo m rather than
among the integers, we may view (11.2) as an equation over the integers modulo m, rather than an equation
over Z, the integers. In this context, the number of solutions of (11.2) is simply the number of solutions in Zm.
Linear Congruence Equation: ax ? 1 (mod m)
First we consider the special linear congruence equation
ax ? 1 (mod m) (11.3)
where a ? 0 (mod m). The complete story of this equation is given in the following theorem (proved in
Problem 11.57).
Theorem 11.26: If a and m are relatively prime, then ax ? 1 (mod m) 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)
Thus x = 4 is our unique solution. (The general solution is 4 + 9k for k ? Z.)
Suppose a solution of (11.3) does exist, that is, suppose gcd(a, m) = 1. Furthermore, suppose the modulus
m is large. Then the Euclidean algorithm can be used to find a solution of (11.3). Specifically, we use the
Euclidean algorithm to find x0 and y0 such that
ax0 + my0 = 1
From this it follows that ax0 ? 1 (mod m); that is, x0 is a solution to (11.3).
280 PROPERTIES OF THE INTEGERS [CHAP. 11
EXAMPLE 11.17 Consider the following congruence equation:
81 ? 1 (mod 256)
By observation or by applying the Euclidean algorithm to 81 and 256, we find that gcd(81, 256) = 1. Thus
the equation has a unique solution. Testing may not be an efficient way to find this solution since the modulus
m = 256 is relatively large. Hence, we apply the Euclidean algorithm to a = 81 and m = 256. Specifically,
as in Example 11.6, we find x0 = ?25 and y0 = 7 such that
81x0 + 256y0 = 1
This means that x0 = ?25 is a solution of the given congruence equation. Adding m = 256 to ?25, we obtain
the following unique solution between 0 and 256:
x = 231
Linear Congruence Equation: ax ? b (mod m)
Now we consider the more general linear congruence equation
ax ? b (mod m) (11.4)
where a ? 0 (mod m). We first consider the case (proved in Problem 11.58) where a and m are coprime.
Theorem 11.27: Suppose a and m are relatively prime. Then ax ? b (mod m) has a unique solution. Moreover,
if s is the unique solution to ax ? 1 (mod m), then the unique solution to ax ? b (mod m) is
x = bs.
EXAMPLE 11.18
(a) Consider the congruence equation 3x ? 5 (mod 8). Since 3 and 8 are coprime, the equation has a unique
solution. Testing the integers 0, 1, . . . , 7, we find that
3(7) = 21 ? 5 (mod 8)
Thus x = 7 is the unique solution of the equation.
(b) Consider the linear congruence equation
33x ? 38 (mod 280) (11.5)
Since gcd(33, 280) = 1, the equation has a unique solution. Testing may not be an efficient way to find this
solution since the modulus m = 280 is relatively large. We apply the Euclidean algorithm to first find a
solution to
33x ? 1 (mod 280) (11.6)
That is, as in Example 11.6, we find x0 = 17 and y0 = 2 to be a solution of
33x0 + 280y0 = 1
This means that s = 17 is a solution of (11.6). Then
sb = 17(38) = 646
is a solution of (11.5). Dividing 646 by m