MODULE 4
Theory of Congruence
Another approach to divisibility questions is through the arithmetic of remainders, or the theory of congruence. The concept and notation that makes it such a powerful tool, was introduced by the German mathematician Carl Friedrich Gauss.
At the end of this chapter, you should be able to:
1. apply the basic properties of congruence in proving mathematical assertions;
2. find special criteria under which a given integer is divisible by another integer; and
3. solve linear and quadratic congruence problems.
4.1 CARL FRIEDRICH GAUSS
Carl Friedrich Gauss introduces the idea of congruence and the notation which makes it such a powerful technique (he explains that he was induced to adopt the @ because of close analogy with algebraic equality). According to Gauss, “If a number n measures the difference between two numbers a and b, then a and b are said to be congruent with respect to n; if not, in-congruent.” Putting this into the form of a definition, we have
Definition 4.1
Let m be any non-zero integer and let a, b be integers. We say that “a is congruent to b modulo m” if m | a – b. In symbol, it is written as a @ b(mod m). If m | a – b, we say that “a is not congruent to b modulo m” and in symbol, we write a @ b(mod m).
Examples:
1) 15 @ 3(mod 4) since 4 divides the difference 15 – 3 =12.
2) 10 @ 15(mod 5) since 5 divides the difference 10 – 15 = -5.
3) 15 @ 3(mod 8) since 8 fails to divide 15 – 3 = 12.
4) 23 @ 12(mod 7) since 7 fails to divide 23 – 12 = 11.
The following are equivalent to each other and may be used interchangeably.
1) a @ b(mod m)
2) m | a – b
3) a = b + mk, for some integer k.
4) a – b @ 0(mod m)
4.2 BASIC PROPERTIES OF CONGRUENCE
Our first theorem provides a useful characterization of congruence modulo m in terms of remainders upon division by m.
Theorem 4-1
If a, b Î Z and n is a positive integer, then a @ b(mod m) if and only if a and b leave the same nonnegative remainder upon division by m.
Proof:
First, take a @ b(mod m), so that a = b + km for some integer k. Upon division by m, b leaves remainder r; that is, b = qm + r, where 0 ≤ r < m. Therefore,
a = b + km
= (qm + r) + km
= qm + km + r
a = (q + k)m + r
which indicates that a has the same remainder as b
On the other hand, suppose we can write a = q1m + r and b = q2m + r, with the same remainder r. Then
a – b = (q1m + r) – (q2m + r)
a – b = (q1 – q2)m
whence m | a – b. In the language of congruences, we have a @ b(mod m).
Illustration:
Consider the integers -56 and -11, since the integers -56 and -11 can be3 expressed in the form
-56 = (-7)9 + 7,
-11 = (-2)9 + 7
with the same remainder 7, Theorem 4.1 tells us -56 @ -11(mod 9). Going in the other direction, the congruence -31 @ 11(mod 7) it implies that -31 and 11 have the same remainder when divided by 7, this is clear from the relations;
-31 = (-5)7 + 4
11 = (1)7 + 4.
Congruence may be viewed as a generalized form of equality. Some of the basic properties of equality that carry over the congruences appear in the next theorem.
Theorem 4-2
Let m > 0 and a, b, c, d be integers. Then the following properties hold:
(1) a @ a(mod m)
(2) If a @ b(mod m), then b @ a(mod m)
(3) If a @ b(mod m) and b @ c(mod m), then a @ c(mod m)
(4) If a @ b(mod m) and c @ d(mod m), then (a + c) @ (b + d)(mod m) and ac @ bd(mod m)
(5) If a @ b(mod m), then (a + c) @ (b + c)(mod m) and ac @ bc(mod m)
(6) If a @ b(mod m), then ak @ bk(mod m) for any positive integer k
(7) If a @ b(mod m) and d | m, d > 0, then a @ b(mod m)
Cancellation, does not hold in congruence.
Illustration:
ax @ ay(mod m) Þ x @ y(mod m)
12 @ 6(mod 6)
6(2) @ 3(2)(mod 6)
6 @ 3(mod 6)
Example: Show that 41 divides 220 – 1.
Solution:
We all know that
25 @ (-9)(mod 41)
(25)4 @ (-9)4(mod 41) by Theorem 4.2(6)
In other words,
220 @ (-9)2 (-9)2(mod 41)
220 @ (81) (81)(mod 41)
220 - 1 @ (81) (81) - 1(mod 41) by Theorem 4.2(5)
but (81) (81) @ 1(mod 41)
220 - 1 @ 1 - 1(mod 41)
220 - 1 @ 0(mod 41)
Thus, 41 | 220 – 1.
Example: Prove that if n is an odd integer, then n2 @ 1(mod 8).
Solution:
Assume that n is an odd integer, it implies that n = 2k + 1 for any integer k.
n = 2k + 1
n2 = (2k + 1)2 Squaring both sides
n2 = 4k2 + 4k + 1
n2 = 4k(k + 1) + 1
but the expression k(k + 1) is always an even number, and it shows that 4k(k +1) is divisible by 8 and the remainder is 1.
Thus, n2 @ 1(mod 8).
Theorem 4-3
Let f(x) be a polynomial with integer coefficients. If a @ b(mod m), then f(a) @ f(b)(mod m).
Proof:
Let f(x) = a0 + a1x + a2x2 + a3x3 + . . . + anxn
where: ai Î Z, i = 0, 1, 2, 3, . . ., n
a @ b(mod m) Þ m | a – b
a0 @ a0(mod m)
a1a @ a1b(mod m)
a2 @ b2(mod m)
a2a2 @ a2b2(mod m)
a3a3 @ a3b3(mod m)
anan @ anbn(mod m)
Adding the corresponding members of the congruences we see that
f(a) @ f(b)(mod m).
4.3 LINEAR CONGRUENCES
An equation of the form ax @ b(mod m) is called a linear congruence, and by a solution of such an equation we mean an integer x0 for which ax0 @ b(mod m). By definition ax0 @ b(mod m) if and only if m | ax0 – b or, what amounts to the same thing, if and only if ax0 – b = ny0 for some integer y0. Thus, the problem of finding all integers which will satisfy the linear congruence ax @ b(mod m) is identical with that of obtaining all solutions of the linear ax – ny = b.
Theorem 4-4
The linear congruence ax @ b(mod m) has a solution if and only if d | b, where d = GCD(a, m). If d | b, then it has d mutually incongruent solutions.
Proof: (left as an exercise)
The given linear congruence ax @ b(mod m) is equivalent to the linear Diophantine equation ax – ny = b. From Therem 2. **, it is known that the latter equation can be solved if and only if d | b; moreover, if it is solvable and x0, y0 is one of the specific solution, then the other solution has the form
x = x0 + (n/d)t , y = y0 - (a/d)t
for some integer t.
Example: Solve the linear congruence 18x @ 30(mod 32).
Solution:
Finding the GCD of 18 and 42 using Euclidean Algorithm.
42 = 18(2) + 6
18 = 6(2) + 6
6 = 6(1) + 0
Therefore, GCD(18, 42) = 6
Since GCD(18, 42) = 6 and 6 divides 30, Theorem 4.4 guarantees the existence of exactly six solutions.
By inspection, one solution is found to be x = 4 and the other solution are given by
x @ [4 + (42/6)t] (mod 42)
x @ [4 + 7t] (mod 42)
where: t = 0, 1, 2, 3, 4 and 5
x @ [4 + 7(0)] (mod 42) Þ x @ 4(mod 42)
x @ [4 + 7(1)] (mod 42) Þ x @ 11(mod 42)
x @ [4 + 7(2)] (mod 42) Þ x @ 18(mod 42)
x @ [4 + 7(3)] (mod 42) Þ x @ 25(mod 42)
x @ [4 + 7(4)] (mod 42) Þ x @ 32(mod 42)
x @ [4 + 7(5)] (mod 42) Þ x @ 39(mod 42)
4.4 QUADRATIC CONGRUENCES
The quadratic congruence means a congruence of the form ax2 + bx + c @ 0(mod n), with a @ 0(mod n).
Theorem 4-5
The quadratic congruence x2 + 1 º 0(mod p), where p is an odd prime, has a solution if and only if p º 1(mod 4).
Proof: (left as an exercise)
Example:
Let us take a look at an actual example; say, the case p = 13, which is prime of the form 4k + 1. Here, we have (p – 1) / 2 = 6 and it is easy to see that
6! = 720 º 5(mod 13),
While
52 + 1 = 26 º 0(mod 13).
Thus the assertion that p -12!2+ 1 ≡0(mod p) is correct for p = 13.
1. Solve each of the following linear congruences. If a solution exists write the general solution.
a. 5x @ 2(mod 26) d. 123x @ 393(mod 57)
b. 36x @ 8(mod 12) e. 140x @ 133(mod 301)
c. 42x @ 50(mod 76)
2. Apply theorem 4.5 to find two solutions to the quadratic congruences x2 º -1(mod 29) and x2 º -1(mod 37).
57