Mathematics for the liberal arts (2013)

Part II. TWO PILLARS OF MATHEMATICS

Chapter 5. NUMBER THEORY

5.13 Congruence

We will generalize the ideas introduced in the last section. This generalization is largely due to Leonhard Euler and Carl Friedrich Gauss. The notation is from an amazing book Gauss published in 1801, when he was 24 years old (and written three years before). It is called Disquisitiones Arithmeticae.

Definitions and Examples

Definition. Let a and b be integers, and m a positive integer. We say that a is congruent to b modulo m if m | (a – b). If this is the case, we write

If a is not congruent to b modulo m, we write

EXAMPLE 5.26

(a) 25 ≡ 17 (mod 4), because 41 (25 – 17)

(b) 6 ≡ – 27 (mod 3), because 31 [6 – (– 27)]

(c) 17 ≡ 117 (mod 7), because 7 (17 – 117)

Basic Properties

a ≡ b (mod m) if and only if there is some integer k such that a = b + km.

Proof. The following statements are equivalent, i.e., each is true if and only if the next is true.

i. a ≡ b (mod m)

ii. m | (a – b)

iii. There is some integer k such that a – b = km.

iv. There is some integer k such that a = b + km.

EXAMPLE 5.27

We saw in the last example that 6 ≡ –27 (mod 3). Let a = 6, b = – 27, m = 3. As promised in the theorem, there is a k such that a = b + km, namely, k = 11. How did we find k? We merely divided 6 – (– 27) by 3.

Congruence shares many properties with equality. (This is the reason for the ≡ notation.) Here are three.

Let a, b, and c be any integers, and m a positive integer. Then

i. (Reflexive) a ≡ a (mod m).

ii. (Symmetric) If a ≡ b (mod m) then b ≡ a (mod m).

iii. (Transitive) If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).

Proof These are all pretty easy. Consider (iii). Suppose that a ≡ b (mod m) and b ≡ c (mod m). Then, by the last result, there are integers k and l such that

Substituting the second of these equations into the first,

which, again by the last result, gives us a ≡ c (mod m).

Here is a useful way of thinking about congruence.

Let a be any integer, and m be a positive integer. Then a is congruent to exactly one of 0,1,…, m – 1, namely, the remainder when we divide a by m.

Proof. Divide a by m, say a = qm + r, with 0 ≤ r < m. By our first basic property above, a ≡ r (mod m). Hence a is congruent to one of 0,1,…, m – 1.

Now suppose that a were congruent to more than one of 0, 1, …, m – 1, say, r and r’. Then we would have, for some k and k’,

But this violates the uniqueness of the Division Theorem. Therefore a is congruent to only one of 0, 1,…, m – 1.

EXAMPLE 5.28

Let a = 234 and m = 4. The remainder when we divide 234 by 4 is 2 (check!), so 234 ≡ 2 (mod 4).

We have to be careful with negative numbers here. We may be tempted to use the last theorem to say that – 9 ≡ 2 (mod 7), because the remainder of 9 is 2 when we divide by 7. But 7 does not divide –9 – 2. Is the theorem wrong? No, because the remainder of – 9 is not 2; it is 5. This is because – 9 = 7(– 2) + 5.

Remainders are also useful for determining when two integers are congruent. Suppose that a and b have the same remainder r on division by m. By the last result, a ≡ r (mod m) and b ≡ r (mod m). Using the symmetric property on the second of these congruences, r ≡ b (mod m). Then using the transitive property on this and the first yields a ≡ b (mod m).

The general result is this.

Let a and b be any integers, m a positive integer. Then a ≡ b (mod m) if and only if they have the same remainder when divided by m.

Definition. The remainder of a upon division by m is called the least residue of a modulo m. The least residue of a is written a mod m.

EXAMPLE 5.29

(a) The least residue of 1,000,009 modulo 10 is 9.

(b) 17 mod 5 = 2

Congruence Classes

Definition. Let a be any integer. The set of all integers congruent to a modulo m is called the congruence class of a modulo m. The congruence class is written [a]_m.

EXAMPLE 5.30

The integers 1,000,009 and 109 belong to the same congruence class mod 10, because they have the same remainder. (Often, people use mod as shorthand for modulo.) The entire congruence class of 1,000,009 modulo 10 is

EXAMPLE 5.31

What are the congruence classes modulo 2? There are two of them, corresponding to the remainders 0 and 1. An integer has remainder 0 if it is divisible by 2, i. e., even. A number has remainder 1 if it is odd. So the congruence classes are the sets of even and odd integers.

EXERCISES

5.69 Determine, for each a, b, and m, whether a ≡ b (mod m). When the answer is yes, find a k such that a = b + km.

a) a = 53, b = 32, m = 7

b) a = 17, b = 2334, m = 15

c) a = – 17, b = 37, m = 9

d) a = 23, b = 0, m = 7

5.70 For each value of a and m, find the least residue of a modulo m. Also find at least four other numbers in the same congruence class as a, at least two of which are negative.

a) a = 17, m = 8

b) a = 87, m = 3

c) a = 5, m = 17

d) a = – 5, m = 17

5.71 A band director wants his band to march in rows of 7, but finds that, when he lines them up, he has only 5 people in the last row. So, after some careful figuring, he thinks that maybe rows of 15 are OK. But when he lines them up in rows of 15, the last row has only one person in it.

a) Assuming that there are no more than 100 people in the band, how many people are there?

b) What does this problem have to do with congruences?

c) What if there might be more than 100 people?