relation [definition / notation]

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.

four examples of relations [info]

###
- equality (=)
- less than (
- less than or equal to (≤)
- divides (i.e. a divides b).

3 properties of equivalence relations [definition]

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

- a ∼ a for all a ∈ A (reflexivity)

- if a ∼ b, then b ∼ a (symmetry)

- if f a ∼ b and b ∼ c, then a ∼ c (transitivity)

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

[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])

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

- a ∈ ...

- a ∼ b ⇐⇒ ...

[proposition]

###
- a ∈ [a]

- a ∼ b ⇐⇒ [a] = [b]

representative of equivalence class

[definition / notation / explanation]

###
- 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])

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

[a] = ?

or

[a]∩[b] = ?

[proposition]

[a] = [b]

or

[a]∩[b] = ∅

partition [definition]

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

- P
_{1}, P_{2}∈ Π, P1 ≠ P2 ⇒ P1 ∩ P2 = ∅

- every a ∈ A belongs to some P ∈ Π

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]

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 Π**absolute value of an interger [definition / notation]

The absolute value of an integer x is defined to be

the division algorithm [theorem]

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.

modulus [definition / notation / explanation]

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)

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

If x ≡ y mod n, we say that x and y are __ equivalent__ modulo n or

__modulo n.__

**congruent**(or sometimes simply equivalent/congruent mod n)

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

###
- equivalence modulo n (i.e. ≡) is an equivalence relation

- the equivalence relation ≡ has exactly n distinct equivalence classes, namely [0], [1], . . . , [n − 1]

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

a + b ≡ ?

and

ab ≡ ?

a + b ≡ a′ + b'

ab ≡ a'b'

addition ⊕ and multiplication ⊙ on Z_{n} are defined as...

[definition / formula]

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

[a] ⊙ [b] = [ab]

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]

Fix an integer n ≥ 2. Addition and multiplication in Z_{n} are ** commutative**,

**, and**

__associative__**. Also, the set Z**

__distributive___{n}has an

__[0], a__

**additive 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__

**multiplicative identity**_{n}.

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

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

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

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

explanation of factors / factorization [definition]

If n = q_{1}q_{2} · · · q_{k} for some q_{1}, q_{2}, . . . , q_{k} ∈ Z, then

the q_{1}, q_{2}, . . . , q_{k} are called *factors* of n,

and the expression n = q_{1}q_{2} · · · q_{k} is called a *factorization* of n.

Suppose m, n ∈ Z; then

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

[proposition]

gcd(m,n) divides both **m **and **n**

Suppose m, n ∈ Z;

then if m and n are not ____ zero,

gcd(m,n) > _ .

[proposition]

Suppose m, n ∈ Z;

then if m and n are not **both** zero,

gcd(m,n) > **0**.

Suppose m, n ∈ Z; then

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

[proposition]

Suppose m, n ∈ Z; then

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

[proposition]

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

gcd(km, kn) = ?

[proposition]

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

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

Euclid's lemma [proposition]

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

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

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

If p|m_{1}m_{2 }· · · m_{k},

then ___ for some _____ .

[corollary]

Suppose k ∈ N, p is a prime, and m_{1}, . . . , m_{k} ∈ N.

If p|m_{1}m_{2} · · · m_{k},

then p|m_{i} for some 1 ≤ i ≤ k.