1 4 7 10 · · · 94 97

2 5 8 11 · · · 95 98

and 4 cards as follows:

···

1 6 11 16 91 96

···

2 7 12 17 92 97

···

3 8 13 18 93 98

···

4 9 14 19 94 99

At the party, ask a person to tell you if their age is odd or even, and then

ask them to tell you on which of the six cards their age appears. Show how

to use this information (and a little common sense) to determine their age.

2.3 Residue classes

As we already observed in Theorem 2.2, for any ¬xed positive integer n, the

binary relation “· ≡ · (mod n)” is an equivalence relation on the set Z. As

such, this relation partitions the set Z into equivalence classes. We denote

the equivalence class containing the integer a by [a]n , or when n is clear from

context, we may simply write [a]. Historically, these equivalence classes are

called residue classes modulo n, and we shall adopt this terminology here

as well.

2.3 Residue classes 21

It is easy to see from the de¬nitions that

[a]n = a + nZ := {a + nz : z ∈ Z}.

Note that a given residue class modulo n has many di¬erent “names”; for

example, the residue class [1]n is the same as the residue class [1 + n]n . For

any integer a in a residue class, we call a a representative of that class.

The following is simply a restatement of Theorem 2.1:

Theorem 2.9. For a positive integer n, there are precisely n distinct residue

classes modulo n, namely, [a]n for a = 0, . . . , n ’ 1.

Fix a positive integer n. Let us de¬ne Zn as the set of residue classes

modulo n. We can “equip” Zn with binary operations de¬ning addition and

multiplication in a natural way as follows: for a, b ∈ Z, we de¬ne

[a]n + [b]n := [a + b]n ,

and we de¬ne

[a]n · [b]n := [a · b]n .

Of course, one has to check this de¬nition is unambiguous, in the sense

that the sum or product of two residue classes should not depend on which

particular representatives of the classes are chosen in the above de¬nitions.

More precisely, one must check that if [a]n = [a ]n and [b]n = [b ]n , then

[a op b]n = [a op b ]n , for op ∈ {+, ·}. However, this property follows

immediately from Theorem 2.3.

It is also convenient to de¬ne a negation operation on Zn , de¬ning

’[a]n := [’1]n · [a]n = [’a]n .

Having de¬ned addition and negation operations on Zn , we naturally de¬ne

a subtraction operation on Zn as follows: for a, b ∈ Z,

[a]n ’ [b]n := [a]n + (’[b]n ) = [a ’ b]n .

Example 2.5. Consider the residue classes modulo 6. These are as follows:

[0] = {. . . , ’12, ’6, 0, 6, 12, . . .}

[1] = {. . . , ’11, ’5, 1, 7, 13, . . .}

[2] = {. . . , ’10, ’4, 2, 8, 14, . . .}

[3] = {. . . , ’9, ’3, 3, 9, 15, . . .}

[4] = {. . . , ’8, ’2, 4, 10, 16, . . .}

[5] = {. . . , ’7, ’1, 5, 11, 17, . . .}

22 Congruences

Let us write down the addition and multiplication tables for Z6 . The addi-

tion table looks like this:

+ [0] [1] [2] [3] [4] [5]

[0] [0] [1] [2] [3] [4] [5]

[1] [1] [2] [3] [4] [5] [0]

[2] [2] [3] [4] [5] [0] [1]

[3] [3] [4] [5] [0] [1] [2]

[4] [4] [5] [0] [1] [2] [3]

[5] [5] [0] [1] [2] [3] [4]

The multiplication table looks like this:

· [0] [1] [2] [3] [4] [5]

[0] [0] [0] [0] [0] [0] [0]

[1] [0] [1] [2] [3] [4] [5]

[2] [0] [2] [4] [0] [2] [4]

[3] [0] [3] [0] [3] [0] [3]

[4] [0] [4] [2] [0] [4] [2]

[5] [0] [5] [4] [3] [2] [1]

2

These operations on Zn yield a very natural algebraic structure whose

salient properties are as follows:

Theorem 2.10. Let n be a positive integer, and consider the set Zn of

residue classes modulo n with addition and multiplication of residue classes

as de¬ned above. For all ±, β, γ ∈ Zn , we have

(i) ± + β = β + ± (addition is commutative),

(ii) (± + β) + γ = ± + (β + γ) (addition is associative),

(iii) ± + [0]n = ± (existence of additive identity),

(iv) ± ’ ± = [0]n (existence of additive inverses),

(v) ± · β = β · ± (multiplication is commutative),

(vi) (± · β) · γ = ± · (β · γ) (multiplication is associative),

(vii) ± · (β + γ) = ± · β + ± · γ (multiplication distributes over addition)

(viii) ± · [1]n = ± (existence of multiplicative identity).

Proof. All of these properties follow easily from the corresponding properties

for the integers, together with the de¬nitions of addition, subtraction, and

multiplication of residue classes. For example, for (i), we have

[a]n + [b]n = [a + b]n = [b + a]n = [b]n + [a]n ,

2.3 Residue classes 23

where the ¬rst and third equalities follow from the de¬nition of addition

of residue classes, and the second equality follows from the commutativity

property of integer addition. The reader may verify the other properties

using similar arguments. 2

An algebraic structure satisfying the conditions in the above theorem is

known more generally as a “commutative ring with unity,” a notion that we

will discuss in Chapter 9.

Note that while all elements of Zn have an additive inverses, not all el-

ements of Zn have a multiplicative inverse. Indeed, for a ∈ Z, the residue

class [a]n ∈ Zn has a multiplicative inverse in Zn if and only if a has a

multiplicative inverse modulo n, which by Theorem 2.4, holds if and only

if gcd(a, n) = 1. Since multiplicative inverses modulo n are uniquely deter-

mined modulo n (see discussion following Theorem 2.5), it follows that if

± ∈ Zn has a multiplicative inverse in Zn , then this inverse is unique, and

we may denote it by ±’1 .

One denotes by Z— the set of all residue classes that have a multiplicative

n

inverse. It is easy to see that Z— is closed under multiplication; indeed,

n

if ±, β ∈ Z— , then (±β)’1 = ±’1 β ’1 . Also, note that for ± ∈ Z— and

n n

β, β ∈ Zn , if ±β = ±β , we may e¬ectively cancel ± from both sides of this

equation, obtaining β = β ” this is just a restatement of the ¬rst part of

Theorem 2.5 in the language of residue classes.

For ± ∈ Zn and positive integer k, the expression ±k denotes the product

± · ± · · · · · ±, where there are k terms in the product. One may extend

this de¬nition to k = 0, de¬ning ±0 to be the multiplicative identity [1]n .

If ± has a multiplicative inverse, then it is easy to see that for any integer

k ≥ 0, ±k has a multiplicative inverse as well, namely, (±’1 )k , which we may

naturally write as ±’k .

In general, one has a choice between working with congruences modulo

n, or with the algebraic structure Zn ; ultimately, the choice is one of taste

and convenience, and it depends on what one prefers to treat as “¬rst class

objects”: integers and congruence relations, or elements of Zn .

An alternative, and somewhat more concrete, approach to de¬ning Zn is

to simply de¬ne it to consist of the n “symbols” 0, 1, . . . , n ’ 1, with addition

and multiplication de¬ned as

a + b := (a + b) mod n, a · b := (a · b) mod n,

for a, b = 0, . . . , n’1. Such a de¬nition is equivalent to the one we have given

here, with the symbol a corresponding to the residue class [a]n . One should

keep this alternative characterization of Zn in mind; however, we prefer the

24 Congruences

characterization in terms of residue classes, as it is mathematically more

elegant, and is usually more convenient to work with.