MAT102 Tutorial W7

• 1
  • Show that $\le$ is not an equivalence relation on the set $\mathbb{Z}$.
  • An equivalence relation is: reflexive, symmetric and transitive.
  • Let's have $\sim$ be $\le$ for this set $\mathbb{Z}$.
  • So to prove reflexivity:
    • Let's have $a\in \mathbb{Z}$.
    • Is $a\sim a$?
    • Yes, because $\sim$ is $\le$ which allows for $a=a$ to be part of this relation.
  • Symmetric:
    • Let's have $a,b\in \mathbb{Z}$.
    • If $a\le b$ is $b\le a$?
    • This only works if $a=b$.
    • Counterexample:
      • $\{\begin{array}{l}a=1\\ b=2\end{array}$
      • $1\le 2$ is true, but $2\le 1$ is not true.
    • Now we don't need to prove anything else, as if one rule for the relation is broken, the whole relation can't be an equivalence relation.
  • Transitivity:
    • We want to show that for $a,b,c\in \mathbb{Z}$ if $a\le b$ and $b\le c$ that $a\le c$
    • Let's set $\mathrm{\Delta }$ to be the change between two numbers $a,b$ that will result in $a+\mathrm{\Delta }ab=b$
    • $a\le b⟹a+\mathrm{\Delta }ab=b$
    • $b\le c⟹b+\mathrm{\Delta }bc=c$
    • $a\le c⟹a+\mathrm{\Delta }ac=c$
    • Let's sub in:
      • $a+\mathrm{\Delta }ab=b$
      • $a+\mathrm{\Delta }ab+\mathrm{\Delta }bc=c$
      • Since the change between $a\to b$ and $b\to c$ is the change between $a\to c$, we can re-express $\mathrm{\Delta }ab+\mathrm{\Delta }bc=\mathrm{\Delta }ac$
      • $a+\mathrm{\Delta }ac=c$
      • So this is transitive.
• 2
  • 1
    • Show $[17]=[-2](\mathrm{mod}19)$
    • This means $19\mid [-2]-[17]$
    • $19\mid -2-17$
    • $19\mid -17-2$
    • $19\mid -19$
    • This is true because $-19=19(-1)$

    ---

    • $-2-17=k(19)$
    • $-19=k(19)$
    • $-\frac{19}{19}=k$
    • $-1=k$
      Okay, let's break down equivalence classes and why [2][3] = [0] can be true in a specific modular arithmetic context. It doesn't mean 2 * 3 = 0 in the way we usually think about numbers. It means something different because of the "mod" operation.

1. What are Equivalence Classes (in Modular Arithmetic)?

• Modular Arithmetic: Modular arithmetic deals with remainders after division. We say "a is congruent to b modulo n" (written as a ≡ b (mod n)) if a and b have the same remainder when divided by n. Equivalently, n divides a - b.

• Equivalence Relation: The "congruent modulo n" relationship (≡ (mod n)) is an equivalence relation. This means it has three key properties:

  • Reflexive: a ≡ a (mod n) (Anything is congruent to itself)
  • Symmetric: If a ≡ b (mod n), then b ≡ a (mod n) (The order doesn't matter)
  • Transitive: If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n) (If two things are congruent to a third, they're congruent to each other)

• Equivalence Classes: Because of these properties, the "congruent modulo n" relationship partitions the integers into equivalence classes. An equivalence class, denoted [a] (mod n), is the set of all integers that are congruent to a modulo n. In other words:

  [a] (mod n) = { x ∈ ℤ | x ≡ a (mod n) } =

  This is saying: The equivalence class [a] contains all numbers that can be written in the form a + (some multiple of n).

2. Examples of Equivalence Classes

• mod 5: Let's look at modulo 5 (n = 5). Here are some equivalence classes:

  • [0] (mod 5) = { …, -10, -5, 0, 5, 10, 15, … } (All multiples of 5)
  • [1] (mod 5) = { …, -9, -4, 1, 6, 11, 16, … } (Multiples of 5, plus 1)
  • [2] (mod 5) = { …, -8, -3, 2, 7, 12, 17, … } (Multiples of 5, plus 2)
  • [3] (mod 5) = { …, -7, -2, 3, 8, 13, 18, … } (Multiples of 5, plus 3)
  • [4] (mod 5) = { …, -6, -1, 4, 9, 14, 19, … } (Multiples of 5, plus 4)

  Notice a few things:

  • There are only five distinct equivalence classes modulo 5.
  • [5] (mod 5) is the same as [0] (mod 5). [6] (mod 5) is the same as [1] (mod 5), and so on. We cycle back around.
  • Every integer belongs to exactly one of these equivalence classes.

• mod 19 (from your previous question):

  • [17] (mod 19) =
  • [-2] (mod 19) = {…, -21, -2, 17, 36, 55, …} These are the same set!

3. Why [2][3] = [0] (mod 6)?

Now we can address your specific example. Your class was likely working modulo 6. The notation [2][3] = [0] (mod 6) means this:

1. Representatives: [2] and [3] represent the equivalence classes of integers congruent to 2 and 3 (mod 6), respectively. We're picking representatives from these classes.

2. Multiplication: When we multiply equivalence classes, we multiply representatives of those classes. So, [2][3] means we're taking 2 (from [2]) and 3 (from [3]) and multiplying them: 2 * 3 = 6.

3. Resulting Equivalence Class: The result of the multiplication (6) then determines the resulting equivalence class. Since 6 ≡ 0 (mod 6) (because 6 leaves a remainder of 0 when divided by 6), the product belongs to the equivalence class [0] (mod 6).

Crucial Point: It's not saying that 2 * 3 = 0 in the usual sense. It's saying that the product of any number from the equivalence class [2] (mod 6) and any number from the equivalence class [3] (mod 6) will always fall into the equivalence class [0] (mod 6).

Example to solidify:

• Choose another representative from [2] (mod 6): Let's say 8 (since 8 = 2 + 1*6).
• Choose another representative from [3] (mod 6): Let's say -3 (since -3 = 3 + (-1)*6).
• Multiply: 8 * (-3) = -24
• Result: -24 ≡ 0 (mod 6) (because -24 = 0 + (-4)*6). See? Still in [0] (mod 6).

In Summary

Equivalence classes in modular arithmetic group numbers based on their remainders. When you perform operations on equivalence classes, you're performing operations on representatives of those classes, and the result is another equivalence class determined by the remainder of the result. The notation might look strange at first, but it's a powerful way to work with remainders. The key is to remember that [a] is not just the number a, it's a whole set of numbers.