discrete_mathematics_with_applications/chapter_8/notes.md

Page 512

Definition

Let R be a relation from A to B. Define the inverse relation R^{-1} from B to A as follows:

 R^{-1} = \{(y, x) \in B \times A | (x, y) \in R\} 

---

Page 513

Definition

A relation on a set A is a relation from A to A.

---

Page 514

Definition

Given sets A_1, A_2, \dots, A_n an $n$-ary relation R on A_1 \times A_2 \times \cdots \times A_n is a subset of A_1 \times A_2 \times \cdots \times A_n. The special cases of $2$-ary, $3$-ary, and $4$-ary relations are called binary, ternary, and quarternary relations, respectively.

---

Page 518

Definition

Let R be a relation on a set A.

1. R is reflexive if, and only if, for every x \in A, x R x.

2. R is symmetric if, and only if, for every x, y \in A, \text{ if } x R y \text{ then } y R x.

3. R is transitive if, and only if, for every x, y, z \in A, \text{ if } x R y \text{ and } y R z \text{ then } x R z.

---

Page 523

Proof of Reflexivity:

Suppose m is a particular but arbitrarily chosen integer. [We must show that m T m.] Now m - m = 0. But 3 | 0 since 0 = 3 \cdot 0. Hence 3 | (m - m). Thus, by definition of T, m T m [as was to be shown].

---

Page 524

Proof of Symmetry:

Suppose m and n are particular but arbitrarily chosen integers that satisfy the condition m T n. [We must show that n T m.] By definition of T, since m T n then 3 | (m - n). By definition of "divides", this means that m - n = 3k, for some integer k. Multiplying both sides by -1 gives n - m = 3(-k). Since -k is an integer, this equation shows that 3 | (n - m). Hence, by definition of T, n T m [as was to be shown].

---

Page 524

Proof of Transitivity:

Suppose m, n, and p are particular but arbitrarily chosen integers that satisfy the condition m T n and n T p. [We must show that m T p.] By definition of T, since m T n and n T p, then 3 | (m - n) and 3 | (n - p). By definition of "divides", this means that m - n = 3r and n - p = 3s, for some integers r and s. Adding the two equations gives (m - n) + (n - p) = 3r + 3s, and simplifying gives that m - p = 3(r + s). Since r + s is an integer, this equation shows that 3 | (m - p). Hence, by definition of T, m T p [as was to be shown].

---

Page 525

Definition

Let A be a set and R a relation on A. The transitive closure of R is the relation R^t on A that satisfies the following three properties:

1. R^t is transitive.

2. R \subseteq R^t.

3. If S is any other transitive relation that contains R, then R^t \subseteq S.

---

Page 529

Definition

Given a partition of a set A, the relation induced by the partition, R, is defined on A as follows: For every x, y \in A,

 x R y \Leftrightarrow \text{ there is a subset } A_i \text{ of the partition such that both } x \text{ and } y \text{ are in } A_i 

---

Page 530

Theorem 8.3.1

Let A be a set with a partition and let R be the relation induced by the partition. Then R is reflexive, symmetric, and transitive.

Proof:

Suppose A is a set with a partition. In order to simplify notation, we assume that the partition consists of only a finite number of sets. The proof for an infinite partition is identical except for notation. Denote the partition subsets by

 A_1, A_2, \dots, A_n 

Then A_i \cap A_j = \emptyset whenever i \neq j, and A_1 \cup A_2 \cup A_3 \cdots \cup A_n = A. The relation R induced by the partition is defined as follows: For every x, y \in A,

 x R y \Leftrightarrow \text{ there is a set } A_i \text{ of the partition such that } x \in A_i \text{ and } y \in A_i 

[Idea for the proof of reflexivity: For R to be reflexive means that each element of a is related by R to itself. But by definition of R, for an element x to be related to itself means that x is in the same subset of the partition itself. Well, if x is in some subset of the partition, then it is certainly in the same subset as itself. And x is in some subset of the partition because the union of the subsets of the partition is all of A. This reasoning is formalized as follows.]

Proof that R is reflexive:

Suppose x \in A. Since A_1, A_2, \dots A_n is a partition of A, it follows that x \in A_i, for for some i, and so the statement

there is a set A_i of the partition such that x \in A_i and x \in A_i

is true. Thus by definition of R, x R x.

[Idea for the proof of symmetry: For R to be symmetric means that any time one element is related to a second, then the second is related to the first. Now for one element x to be related to a second element y means that x and y are in the same subset of the partition. But if this is the case, then y is in the same subset of the partition as x, so y is related to x by definition of R. This reasoning is formalized as follows.]

Proof that R is symmetric:

Suppose x and y are elements of A such that x R y. Then there is a subset A_i of the partition such that x \in A_i and y \in A_i by definition of R. It follows that the statement

there is a subset A_i of the partition such that y \in A_i and x \in A_i

is also true. Hence, by definition of R, y R x.

[Idea for the proof of transitivity: For R to be transitive means that any time one element of A is related by R to a second and that second is related to a third, then the first element is related to the third. But for one element to be related to another means that there is a subset of the partition that contains both. So suppose x, y, and z are elements such that x is in the same subset as y and y is in the same subset as z. Must x be in the same subset as z? Yes, because the subsets 9f the partition are mutually disjoint. Since the subset that contains x and y has an element in common with the subset that contains y and z (namely, y), the two subsets are equal. But this means that x, y, and z are all in the same subset, and so, in particular, x and z are in the same subset. Hence x is related by R to z. This reasoning is formalized as follows.]

Proof that R is transitive:

Suppose x, y, and z are in A and x R y and y R z. By definition of R, there are subsets A_i and A_j of the partition such that

 x \text{ and } y  \text{ are in } A_i \quad \text{ and } \quad y \text{ and } z \text{ are in } A_j 

Suppose A_i \neq A_j. [We will deduce a contradiction.] Then A_i \cap A_j = \emptyset since \{A_1, A_2, A_3, \dots, A_n\} is a partition of A. But y is in A_i and y is in A_j also. Hence A_i \cap A_j \neq \emptyset. [This contradicts the statement that A_i \cap A_j = \emptyset.] Thus A_i = A_j. It follows that x, y, and z are all in A_i, and so, in particular,

 x \text{ and } z \text{ are in } A_i 

Thus x R z by definition of R.

---

Page 531

Definition

Let A be a set and R a relation on A. R is an equivalence relation if, and only if, R is reflexive, symmetric, and transitive.

---

Page 533

Definition

Suppose A is a set and R is an equivalence relation on A. For each element a in A, the equivalence class of $a$, denoted [a] and called the class of $a$ for short, is the set of all elements x in A such that x is related to a by R.

In symbols:

 [a] = \{x \in A | x R a\} 

---

Page 536

Lemma 8.3.2

Suppose A is a set, R is an equivalence relation on A, and a and b are elements of A. If a R b, then [a] = [b].

---

Page 536

Proof of Lemma 8.3.2

Let A be a set, let R be an equivalence relation on A, and suppose

 a \text{ and } b \text{ are elements of } A \text{ such that } a R b 

[We must show that [a] = [b].]

Proof that [a] \subseteq [b]:

Let x \in [a]. [We must show that x \in [b].]

Since

 x \in [a] 

then

 x R a 

by definition of class. But

 a R b 

by hypothesis. Thus, by transitivity of R,

 x R b 

Hence

 x \in [b] 

by definition of class. [This is what was to be shown.]

**Proof that [b] \subseteq [a].

Let x \in [b]. [We must show that x \in [a].]

Since

 x \in [b] 

then

 x R b 

by definition of class. Now

 a R b 

by hypothesis. Thus, since R is symmetric,

 b R a 

also. Then, since R is transitive and x R b and b R a,

 x R a 

Hence,

 x \in [a] 

by definition of class. [This is what was to be shown.]

Since [a] \subseteq [b] and [b] \subseteq [a], it follows that [a] = [b] by definition of set equality.

---

Page 537

Lemma 8.3.3

If A is a set, R is an equivalence relation on A, and a and b are elements of A, then

 \text{either } [a] \cap [b] = \emptyset \quad \text{ or } \quad [a] = [b] 

---

Page 537

Proof of Lemma 8.3.3

Suppose A is a set, R is an equivalence relation on A, a and b are elements of A, and

 [a] \cap [b] \neq \emptyset 

[We must show that [a] = [b].]

Since [a] \cap [b] \neq \emptyset, there exists an element x in A such that x \in [a] \cap [b]. By definition of intersection,

 x \in [a] \quad \text{ and } \quad x \in [b]

and so

 x R a \quad \text{ and } \quad x R b 

by definition of class. Since R is symmetric [being an equivalence relation] and x R a, then a R x. But R is also transitive [since it is an equivalence relation], and so, since a R x and x R b,

 a R b 

Now A and b satisfy the hypothesis of Lemma 8.3.2. Hence, by that lemma,

 [a] = [b] 

[as was to be shown].

---

Page 537

Theorem 8.3.4 The Partition Induced by an Equivalence Relation

If A is a set and R is an equivalence relation on A, then the distinct equivalence classes of R form a partition of A; that is, the union of the equivalence classes is all of A, and the intersection of any two distinct classes is empty.

---

Page 538

Proof of Theorem 8.3.4

Suppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote

 A_1, A_2, \dots, A_n 

where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.)

Proof that A = A_1 \cup A_2 \cup \cdots \cup A_n:

[We must show that A \subseteq A_1 \cup A_2 \cup \cdots \cup A_n and that A_1 \cup A_2 \cup \cdots \cup A_n \subseteq A.]

To show that A \subseteq A_1 \cup A_2 \cup \cdots \cup A_n, suppose x is any element of A. [We must show that x \in A_1 \cup A_2 \cup \cdots A_n.] By reflexivity of R, x R x. And this implies that x \in [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A_1, A_2, \dots, or A_n. Thus x \in A_i for some index i, and hence x \in A_1 \cup A_2 \cup \cdots \cup A_n by definition of union [as was to be shown].

To show that A_1 \cup A_2 \cup \cdots \cup A_n \subseteq A, suppose x \in A_1 \cup A_2 \cup \cdots \cup A_n. [We must show that x \in A.] Then x \in A_i for some i = 1, 2, \dots, n, by definition of union. Now each A_i is an equivalence class of R, and equivalence classes are subsets of A. Hence A_i \subseteq A and so x \in A [as was to be shown].

Since A \subseteq A_1 \cup A_2 \cup \cdots A_n and A_1 \cup A_2 \cup \cdots \cup A_n \subseteq A, then by definition of set equality, A = A_1 \cup A_2 \cup \cdots \cup A_n.

Proof that the distinct classes of R are mutually disjoint:

Suppose that A_i and A_j are any two distinct equivalence classes of R. [We must show that A_i and A_j are disjoint.] Since A_i and A_j are distinct, then A_i \neq A_j. And since A_i and A_j are equivalence classes of R, there must exist elements a and b in A such that A_i = [a] and A_j = [b].

By Lemma 8.3.3,

 \text{either } [a] \cap [b] = \emptyset \quad \text{ or } \quad [a] = [b]

Now [a] \neq [b] because A_i \neq A_j, and hence [a] \cap [b] = \emptyset. Thus A_i \cap A_j = \emptyset, and so A_i and A_j are disjoint [as was to be shown].

---

Page 540

Definition

Suppose R is an equivalence relation on a set A and S is an equivalence class of R. A representative of the class S is any element a such that [a] = S.

--

Page 541

Definition

Let m and n be integers and let d be a positive integer. We say that m is congruent to n modulo $d$ and write

 m = n (\mod d) 

if, and only if,

 d | (m - n) 

Symbolically:

 m \equiv n(\mod d) \Leftrightarrow d | (m - n) 

---

Page 542

Example 8.3.12

_Rational Numbers are Really Equivalence Classes

Let A be the set of all ordered pairs of integers for which the second element of the pair is nonzero. Symbolically:

 A = \mathbb{Z} \times (\mathbb{Z} - \{0\}) 

Define a relation R on A as follows: For all pairs (a, b) and (c, d) in A,

 (a, b) R (c, d) \Leftrightarrow ad = bc 

The fact is that R is an equivalence relation.

---

Page 549

Theorem 8.4.1 Modular Equivalences

Let a, b, and n be any integers and suppose n > 1. The following statements are all equivalent:

1. n | (a - b)

2. a \equiv b (\mod n)

3. a = b + kn for some integer k

4. a and b have the same (nonnegative) remainder when divided by n

5. a \mod n = b \mod n

Proof:

We will show that (1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (4) \Rightarrow (5) \Rightarrow (1). It will follow by the transitivity of if-then that all five statements are equivalent.

So let a, b, and n be any integers with n > 1.

Proof that (1) \Rightarrow (2):

Suppose that n | (a - b). By definition of congruence module n, we can immediately conclude that a \equiv b (\mod n).

Proof that (2) \Rightarrow (3):

Suppose a \equiv b (\mod n). By definition of congruence modulo n, n | (a - b). Thus, by definition of divisibility, a - b = kn, for some integer k. Adding b to both sides gives that a = b + kn.

Proof that (3) \Rightarrow (4):

Suppose that a = b + kn, for some integer k. Use the quotient-remainder theorem to divide a by n to obtain

 a = qn + r \text{ where } q \text{ and } r \text{ are integers and } 0 \leq r < n 

So r is the remainder obtained when a is divided by n. Substituting b + kn for a in the equation a = qn + r gives that

 b + kn = qn + r 

and subtracting kn from both sides and factoring out n yields

 b = (q - k)n + r 

Now since 0 \leq r < n, the uniqueness property of the quotient-remainder theorem guarantees that r is also the remainder obtained when b is divided by n. Thus a and b have the same remainder when divided by n.

Proof that (4) \Rightarrow (5):

Suppose that a and b have the same remainder when divided by n. It follows immediately from the definition of the \mod function that a \mod n = b \mod n.

Proof that (5) \Rightarrow (1):

Suppose that a \mod n = b \mod n. By definition of the \mod function, a and b have the same remainder when divided by n. Thus, by the quotient-remainder theorem, we can write

 a = q_1n + r \text{ and } b = q_2n + r \text{ where } q_1, q_2 \text{ and } r \text{ are integers and } 0 \leq r < n 

It follows that

 a - b = (q_1n + r) - (q_2n + r) = (q_1 - q_2)n 

Therefore, since q_1 - q_2 is an integer, n | (a - b).

---

Page 550

Definition

Given integers a and n with n > 1, the residue of a modulo $n$ is a \mod n, the nonnegative remainder obtained when a is divided by n. The numbers 0, 1, 2, \dots, n - 1 are called a complete set of residues modulo $n$. To reduce a number modulo $n$ means to set it equal to its residue modulo n. If a modulus n > 1 is fixed throughout a discussion and an integer a is given, the words "modulo $n$" are often dropped and we simply speak of the residue of $a$.

---

Page 550

Theorem 8.4.2 Congruence Modulo n Is an Equivalence Relation

If n is any integer with n > 1, congruence modulo n is an equivalence relation on the set of all integers. The distinct equivalence classes of the relation are the sets [0], [1], [2], \dots, [n - 1], where for each a = 0, 1, 2, \dots, n - 1,

 [a] = \{m \in \mathbb{Z} | m \equiv a (\mod n)\} 

or, equivalently,

 [a] = \{m \in \mathbb{Z} | m = a + kn \text{ for some integer } k\} 

Proof:

Suppose n is any integer with n > 1. We must show that congruence modulo n is reflexive, symmetric, and transitive.

Proof of reflexivity:

Suppose a is any integer. To show that a \equiv a (\mod n), we must show that n | (a - a). Now a - a = 0, and n | 0 because 0 = n \cdot 0. Therefore a \equiv a (\mod n).

Proof of symmetry:

Suppose a and b are any integers such that a \equiv b(\mod n). We must show that b \equiv a (\mod n). Now since a \equiv b(\mod n), then n | (a - b). Thus, by definition of divisibility, a - b = nk, for some integer k. Multiplying both sides of this equation by -1 to obtain

 -(a - b) = -nk 

or, equivalently,

 b - a = n(-k) 

Thus, by definition of divisibility n | (b - a), and so, by definition of congruence modulo n, b \equiv a (\mod n).

Proof of transitivity:

This is left as exercise 5 at the end of the section.

Proof that the distinct equivalence classes are [0], [1], [2], \dots, [n - 1]:

This is left as exercise 6 at the end of the section.

---

Page 551

Theorem 8.4.3 Modular Arithmetic

Let a, b, c, d, and n be integers with n > 1, and suppose

 a \equiv c (\mod n) \text{ and } b \equiv d(\mod n) 

Then

1. (a + b) \equiv (c + d)(\mod n)

2. (a - b) \equiv (c - d)(\mod n)

3. ab \equiv cd(\mod n)

4. a^m \equiv c^m(\mod n) for every positive integer m

Proof:

Because we will make greatest use of part 3 of this theorem, we prove it here and leave the proofs of the remaining parts of the theorem to exercises 9-11 at the end of the section.

_Proof of Part 3:_Proof Suppose a, b, c, d, and n are integers with n > 1, and suppose a \equiv b(\mod n) and c \equiv d(\mod n). By Theorem 8.4.1, there exists integers s and t such that

 a = c + sn \text{ and } b = d + tn 

Then

 ab = (c + sn)(d + tn) 

 = cd + ctn + snd + sntn 

 = cd + n(ct + sd + stn) 

Let k = ct + sd + stn. Then k is an integer because it is a sum of products of integers, and ab = cd + nk. Thus by Theorem 8.4.1, ab \equiv cd(\mod n).

---

Page 552

Corollary 8.4.4

Let a, b, and n be integers with n > 1. Then

 ab \equiv [(a \mod n)(b \mod n)](\mod n) 

or, equivalently,

 ab \mod n = [(a \mod n)(b \mod n)]\mod n 

In particular, if m is a positive integer, then

 a^m \equiv [(a \mod n)^m](\mod n) 

---

Page 554

Example 8.4.4 Computing a^k \mod n When k is a Power of $2$

Find 144^4 \mod 713.

Solution

Use property (8.4.1) to write 144^4 = (144^2)^2. Then

 144^4 \mod 713 = (144^2)^2 \mod 713 

 = (144^2 \mod 713)^2 \mod 713 

 = (20736 \mod 713)^2 \mod 713 \text{ because } 144^2 = 20736 

 = 59^2 \mod 713 \text{ because } 20736 \mod 713 =  59 

 = 3481 \mod 713 \text{ because } 59^2 = 3481 

 = 629 \text{ because } 3481 \mod 713 = 629 

---

Page 554

Example 8.4.5 Computing a^k \mod n When k is Not a Power of $2$

Find 12^{43} \mod 713.

Solution

First write the exponent as a sum of powers of 2:

 43 = 2^5 + 2^3 + 2 + 1 = 32 + 8 + 2 + 1 

Next compute 12^{2^k} for k = 0, 1, 2, 3, 4, \text { and } 5.

 12 \mod 713 = 12 

 12^2 \mod 713 = 144 

 12^4 \mod 713 = 144^2 \mod 713 = 59 \text{ by Example 8.4.4} 

 12^8 \mod 713 = 59^2 \mod 713 = 629 \text{ by Example 8.4.4} 

 12^{16} \mod 713 = 629^2 \mod 713 = 639 \text{ by the method of Example 8.4.4} 

 12^{32} \mod 713 = 639^2 \mod 713 = 485 \text{ by the method of Example 8.4.4} 

By property (8.4.2),

 12^{43} = 12^{32 + 8 + 2 + 1} = 12^{32} \cdot 12^8 \cdot 12^2 \cdot 12^1 

Thus, by Corollary 8.4.4,

 12^{43} \mod 713 = \{(12^{32} \mod 713) \cdot (12^8 \mod 713) \cdot (12^2 \mod 713) \cdot (12 \mod 713)\} \mod 713 

By substitution,

 12^{43} \mod 713 = (485 \cdot 629 \cdot 144 \cdot 12) \mod 713 

 = 527152320 \mod 713 

 = 48 

---

Page 555

Definition

An integer d is said to be a linear combination of integers a and b if, and only if, there exist integers s and t such that as + bt = d.

---

Page 555

Theorem 8.4.5 Writing a Greatest Common Divisor as a Linear Combination

For all integers a and b, not both zero, if d = \text{gcd}(a, b), then there exist integers s and t such that as + bt = d.

Proof:

Given integers a and b, not both zero, and given d = \text{gcd}(a, b), let

 S = \{x | x \text{ is a positive integer and } x = as + bt \text{ for some integers } s \text{ and } t\} 

Note that S is a nonempty set because (1) if a > 0 then 1 \cdot a + 0 \cdot b \in S, (2) if a < 0 then (-1) \cdot a + 0 \cdot b \in S, and (3) if a = 0 then, by assumption, b \neq 0, and hence 0 \cdot a + 1 \cdot b \in S or 0 \cdot a + (-1) \cdot b \in S. Thus, because S is a nonempty subset of positive integers, by the well-ordering principle for the integers there is a least element c in S. By definition of S,

 c = as + bt \text{ for some integers } s \text{ and } t 

We will show that (1) c \geq d, and (2) c \leq d, and we will therefore be able to conclude that c = d = \text{gcd}(a, b).

(1) Proof that c \geq d:

[In this part of the proof, we show that d is a divisor of c and thus that d \leq c.] Because d = \text{gcd}(a, b), by definition of greatest common divisor, d | a and d | b. Hence a = dx and b = dy for some integers x and y. Then

 c = as + bt 

 = (dx)s + (dy)t 

 = d(xs + y) 

Now xs + yt is an integer because it is a sum of products of integers. Thus, by definition of divisibility, d | c. Both c and d are positive, and hence, by Theorem 4.4.1, c \geq d.

(2) Proof that c \leq d:

[In this part of the proof, we show that c is a divisor of both a and b and therefore that c is less than or equal to the greatest common divisor of a and b, which is d.] Apply the quotient-remainder theorem to the division of a by c to obtain

 a = cq + r \text{ for some integers } q \text{ and } r \text{ with } 0 \leq r < c 

Thus for some integers q and r with 0 \leq r < c,

 r = q - cq 

Now c = as + bt. Therefore, for some integers q and r with 0 \leq r < c,

 r = a - (as + bt)q 

 = a(1 - sq) - btq 

Thus r is a linear combination of a and b. If r > 0, then r would be in S, and so r would be a smaller element of S than c, which would contradict the fact that c is the least element of S. Hence r = 0. By substitution into (8.4.4),

 a = cq 

and therefore c | a.

An almost identical argument establishes that c | b and is left as exercise 30 at the end of the section.

Because c | a and c | b, c is a common divisor of a and b. Hence c is less than or equal to the greatest common divisor of a and b. In other words, c \leq d.

From (1) and (2), we conclude that c = d. It follows that d, the greatest common divisor of a and b, is equal to as + bt.

---

Page 557

Definition

Given any integer a and any positive integer n, if there exists an integer s such that as \equiv 1(\mod n), then s is called an inverse for a modulo n.

---

Page 557

Definition

Integers a and b are relatively prime if, and only if, \text{gcd}(a, b) = 1. Integers a_1, a_2, a_3, \dots, a_n are pairwise relatively prime if, and only if, \text{gcd}(a_i, a_j) = 1 for all integers i and j with 1 \leq i, j \leq n, and i \neq j.

---

Page 557

Corollary 8.4.6

If a and b are relatively prime integers, then there exist integers s and t such that as + bt = 1.

---

Page 558

Corollary 8.4.7 Existence of Inverses Modulo $n$

For all integers a and n, if \text{gcd}(a, n) = 1, then there exists an integer s such that as \equiv 1(\mod n), and so s is an inverse for a modulo n.

Proof:

Suppose a and n are integers and \text{gcd}(a, n) = 1. By Corollary 8.4.6, there exist integers s and t such that

 as + nt = 1 

Subtracting nt from both sides gives that

 as = 1 - nt = 1 + (-t)n 

Thus, by definition of congruence modulo n,

 as \equiv 1(\mod n) 

---

Page 562

Theorem 8.4.8 Euclid's Lemma

For all integers a, b, and c, if \text{gcd}(a, c) = 1 and a | bc, then a | b.

Proof:

Suppose a, b, and c are integers, \text{gcd}(a, c) = 1, and a | bc. [We must show that a | b.] By Theorem 8.4.5, there exist integers s and t so that

 as + ct = 1 

Multiply both sides of this equation by b to obtain

 bas + bct = b 

Since a | bc, by definition of divisibility there exists an integer k such that

 bc = ak 

Substituting (8.4.8) into (8.4.7), rewriting, and factoring out an a gives that

 b = bas + (ak)t = a(bs + kt) 

Let r = bs + kt. Then r is an integer (because b, s, k, and t are all integers), and b = ar. Thus a | b by definition of divisibility.

Page 562

Theorem 8.4.9 Cancellation Theorem for Modular Congruence

For all integers a, b, and c, and n with n > 1, if \text{gcd}(c, n) = 1 and ac = bc(\mod n), then a \equiv b(\mod n).

Proof:

Suppose a, b, c, and n are integers, \text{gcd}(c, n) = 1, and ac \equiv bc(\mod n). [We must show that a \equiv b(\mod n).] By definition of congruence modulo n,

 n | (ac - bc) 

and so, since

 ac - bc = (a - b)c 

then

 n | (a - b)c 

Because \text{gcd}(c, n) = 1, we may apply Euclid's lemma to obtain

 n | (a - b) 

and so, by definition of congruence modulo n,

 a \equiv b(\mod n) 

---

Page 563

Theorem 8.4.10 Fermat's Little Theorem

If p is any prime number and a is any integer such that p \cancel{|} a, then a^{p - 1} \equiv 1(\mod p).

Proof:

Suppose p is any prime number and a is any integer such that p \cancel{|} a. Note that a \neq 0 because otherwise p would divide a. Consider the set of integers

 S = \{a, 2a, 3a, \dots, (p - 1)a\} 

We claim that no two elements of S are congruent modulo p. For suppose sa \equiv ra(\mod p) for some integers s and r with 1 \leq r < s \leq p - 1. Then, by definition of congruence modulo p,

 p | (sa - ra) \text{ or, equivalently, } p | (s - r)a 

Now p \cancel{|} a by hypothesis, and because p is prime, \text{gcd}(a, p) = 1. Thus, by Euclid's lemma, p | (s - r), But this is impossible because 0 < s - r < p.

Consider the function F from S to the set T = \{1, 2, 3, \dots, (p - 1)\} that sends each element of S to its residue modulo p. Then F is one-to-one because no two elements of S are congruent modulo p. In Section 9.4 we prove that if a function from one finite set to another is one-to-one, then it is also onto. Hence F is onto, and so p - 1 residues of the p - 1 elements of S are exactly the numbers 1, 2, 3 \dots, (p - 1).

It follows by Theorem 8.4.3(3) that

 a \cdot 2a \cdot 3a \cdots (p - 1)a \equiv [1 \cdot 2 \cdot 3 \cdots (p - 1)](\mod p) 

or, equivalently,

 a^{p - 1}(p - 1)! \equiv (p - 1)!(\mod p) 

Now because p is prime, p and (p - 1)! are relatively prime. Thus, by the cancellation theorem for modular congruence (Theorem 8.4.9),

 a^{p - 1} \equiv 1(\mod p)