Chapter 6

Question 1

relation [definition / notation]

Answer 1

A relation on a set A is a subset of A × A.

If R ⊆ A × A is a relation on A, we usually write xRy to indicate that (x, y) ∈ R and we say that x is related to y by the relation R.

So xRy ⇐⇒ (x, y) ∈ R.

We often use other symbols instead of R, such as ∼, ≈, ≡, , ≥, ≺, ≻, etc.

Question 2

four examples of relations [info]

Answer 2

1. equality (=)
2. less than (
3. less than or equal to (≤)
4. divides (i.e. a divides b).

Question 3

3 properties of equivalence relations [definition]

Answer 3

A relation ∼ on a set A is an equivalence relation if:

1. a ∼ a for all a ∈ A (reflexivity)
2. if a ∼ b, then b ∼ a (symmetry)
3. if f a ∼ b and b ∼ c, then a ∼ c (transitivity)

Question 4

If ∼ is an equivalence relation on A, then the equivalence class of a ∈ A is… [definition / notation]

Answer 4

[a] := {b ∈ A : b ∼ a}

(note: sometimes, when we wish to emphasize the particular equivalence relation (for instance, when we are working with more than one), we write [a]∼ instead of [a])

Question 5

Suppose ∼ is an equivalence relation on a set A, and a, b ∈ A; then…

1. a ∈ …
2. a ∼ b ⇐⇒ …

[proposition]

Answer 5

1. a ∈ [a]
2. a ∼ b ⇐⇒ [a] = [b]

Question 6

representative of equivalence class
[definition / notation / explanation]

Answer 6

• we say that a is a representative of the equivalence class [a]
• representatives of a given equivalence class are not unique in general
• b is a representative of the equivalence class [a] if and only if a ∼ b (which is equivalent to b ∈ [a])

Question 7

Suppose ∼ is an equivalence relation on a set A. Then, for all a, b ∈ A, we have…

[a] = ?

or

[a]∩[b] = ?

[proposition]

Answer 7

[a] = [b]

or

[a]∩[b] = ∅

Question 8

partition [definition]

Answer 8

A partition of a set A is a set Π, whose elements are nonempty subsets of A such that…

• P₁, P₂ ∈ Π, P1 ≠ P2 ⇒ P1 ∩ P2 = ∅
• every a ∈ A belongs to some P ∈ Π

Question 9

Suppose ∼ is an equivalence relation on A. Then the set Π of equivalence classes of ∼ is a _________ of A.

Suppose Π is a _________ of A. Then the relation ∼ defined by
a ∼ b ⇔ a and b lie in the same ____________.

[proposition]

Answer 9

Suppose ∼ is an equivalence relation on A. Then the set Π of equivalence classes of ∼ is a partition of A.

Suppose Π is a partition of A. Then the relation ∼ defined by
a ∼ b ⇔ a and b lie in the same element of Π .

Question 10

absolute value of an interger [definition / notation]

Answer 10

The absolute value of an integer x is defined to be

Question 11

the division algorithm [theorem]

Answer 11

Suppose n ∈ N. For every m ∈ Z, there exist a unique q, r ∈ Z such that…

• m = qn + r
• 0 ≤ r ≤ n − 1

The integer q is called the quotient and r is called the remainder upon division of m by n.

Question 12

modulus [definition / notation / explanation]

Answer 12

For a fixed n ∈ N, we define a relation ≡ on Z by

x ≡ y ⇔ x − y is divisible by n .

The natural number n is called the modulus.

(note: when we wish to make the modulus explicit, we write
x ≡ y mod n)

Question 13

If x ≡ y mod n, we say that x and y are __________ modulo n or _________ modulo n. [terminology]

Answer 13

If x ≡ y mod n, we say that x and y are equivalent modulo n or congruent modulo n.

(or sometimes simply equivalent/congruent mod n)

Question 14

fix a modulus n ∈ N (2 points) [proposition]

Answer 14

1. equivalence modulo n (i.e. ≡) is an equivalence relation
2. the equivalence relation ≡ has exactly n distinct equivalence classes, namely [0], [1], . . . , [n − 1]

Question 15

Fix a modulus n ∈ N. If a ≡ a′ and b ≡ b′ , then

a + b ≡ ?

and

ab ≡ ?

Answer 15

a + b ≡ a′ + b’

ab ≡ a’b’

Question 16

addition ⊕ and multiplication ⊙ on Z_n are defined as…
[definition / formula]

Answer 16

[a] ⊕ [b] = [a + b]

[a] ⊙ [b] = [ab]

Question 17

Fix an integer n ≥ 2. Addition and multiplication in Z_n are ___________, ___________, and ____________. Also, the set Z_n has a ________identity (0), a ______________ identity(1) and ________ inverses (the additive inverse of (a) being ____.) [completion]

Answer 17

Fix an integer n ≥ 2. Addition and multiplication in Z_n are commutative**, **associative**, and **distributive. Also, the set Z_n has an additive identity [0], a multiplicative identity [1], and additive inverses (the additive inverse of [a] being [−a]). In other words, Axioms 1.1–1.4 hold with Z replaced everywhere by Z_n.

Question 18

An integer n ≥ 2 is prime if it is divisible only by __ and __. [definition]

Answer 18

An integer n ≥ 2 is prime if it is divisible only by ±1 and ±n.

Question 19

If an integer n ≥ 2 is not prime, it is _________. [definition]

Answer 19

If an integer n ≥ 2 is not prime, it is composite.

Question 20

explanation of factors / factorization [definition]

Answer 20

If n = q₁q₂ · · · q_k for some q₁, q₂, . . . , q_k ∈ Z, then

the q₁, q₂, . . . , q_k are called factors of n,

and the expression n = q₁q₂ · · · q_k is called a factorization of n.

Question 21

Suppose m, n ∈ Z; then

gcd(m,n) divides both _ and _ .

[proposition]

Answer 21

gcd(m,n) divides both m and n

Question 22

Suppose m, n ∈ Z;

then if m and n are not ____ zero,

gcd(m,n) > _ .

[proposition]

Answer 22

Suppose m, n ∈ Z;

then if m and n are not both zero,

gcd(m,n) > 0.

Question 23

Suppose m, n ∈ Z; then

every interger that divides both m and n also divides ________ .

[proposition]

Answer 23

Suppose m, n ∈ Z; then

every interger that divides both m and n also divides gcd(m, n).

[proposition]

Question 24

for all k, m, n ∈ Z, we have

gcd(km, kn) = ?

[proposition]

Answer 24

for all k, m, n ∈ Z, we have

gcd(km, kn) = |k|gcd(m,n)

Question 25

Euclid’s lemma [proposition]

Answer 25

Suppose p is a prime and m, n ∈ N.

If p|mn, then p|m or p|n

Question 26

Suppose k ∈ N, p is a prime, and m1, . . . , mk ∈ N.

If p|m₁m₂ · · · m_k,

then ___ for some _____ .

[corollary]

Answer 26

Suppose k ∈ N, p is a prime, and m₁, . . . , m_k ∈ N.

If p|m₁m₂ · · · m_k,

then p|m_i for some 1 ≤ i ≤ k.