Home MATH 235 Monday, October 1, 2012

Monday, October 1, 2012 CC-BY-NC
Congruence classes

Maintainer: admin

Lecture notes for lecture #12 of MATH 235, taught by Henri Darmon. These lecture notes are student-generated and any errors or omissions should be assumed to be the fault of the notetaker and not of the lecturer. To correct an error, you have to be registered and logged-in; alternatively, you can contact @dellsystem directly.

In this lecture, we continued section 13 of the notes.

1Congruence relation notation

First, a brief note on notation for congruence relations. $a \equiv b \,(\text{mod } n)$ is Gauss' notation, and this is what we've been using. We can also write, as shortland, $a \equiv_n b$. Alternatively, if the $n$ can be inferred from the context, we can omit it entirely (so $a \equiv b$).

2Introduction to congruence classes

As we went over last time, a congruence relation is an equivalence relation on $\mathbb{Z}$. The set of equivalence classes for such a relation, or congruence classes, is denoted by $\mathbb{Z}/n\mathbb{Z}$. Each congruence class can be written in the form $\{a \in \mathbb{Z}: a + n\mathbb{Z}\}$ (where $a$ is the thing in the set).

Informally, we can say that the elements of a congruence class have the same remainder when divided by $n$. So $\{0, n, 2n, 3n, \ldots\}$ would be one class, and $\{1, n+1, 2n+1, 3n+1,\ldots\}$ would be another, and so on.

We can formally express an congruence class with equivalence class notation: that is, $[a]$ denotes the equivalence class of which $a$ is an element.

Two things that are congruent to each other are necessarily in the same equivalence class: $a \equiv a'$ means that $[a] = [a']$ and vice versa.

2.1A complete set of representatives

As was mentioned last time, a complete set of representatives for this relation is given by $\{0, 1, \ldots n-1\}$. Why is this? Well, because a number in that set will be the residue/remainder that results when any number is divided by $n$. We can write $a$ as $a = qn + r$, where $r < n$; this means that $r$ can be $0, 1, \ldots n-1$. Clearly, $a \equiv_n r$, as $a - r = qn$ which is divisible by $n$. Consequently, by the previous section, $[a] = [r]$. This means that $\{[0], [1], [2], \ldots [n-1]\}$ is the set of all equivalence classes for this congruence relation, which also tells us that the cardinality of this set (and so the number of equivalence classes) is equal to $n$.

2.2Addition and multiplication

If $a \equiv_n a'$, and $b \equiv_n b'$, then $a + b \equiv_n a' + b'$.

Similarly, $a \cdot b \equiv_n a' \cdot b'$.

The proof of closure under addition follows directly from the definition of congruence. $(a + b) - (a' + b') = (a-a') + (b-b')$ (by associativity and commutativity in $\mathbb{Z}$). We know that $n | (a-a')$, and $n|(b-b')$, so the sum of the two is divisible by $n$.

For multiplication, we can first show that $ab - a'b = b(a-a')$. Since $n|a-a'$, it must also be that $n|b(a-a')$, and so $ab \equiv a'b$. Then, by similar manipulation, we can show that $a'b \equiv a'b'$. By the transitivity of congruence, we then have that $ab \equiv a'b'$.

Alternatively, we can add $0$ to the expression $ab - ab'$ for a slightly more artificial (but equally valid) proof:

$$ab - a'b' + (ab' - ab') = ab - ab' + ab' - a'b' = \underbrace{a(b-b')}_{\text{divisible by } n} + \underbrace{b'(a-a')}_{\text{divisible by } n} \, \blacksquare$$

2.2.1Applications to congruence classes

As a result of the previous section, we can define addition and multiplication on the congruence classes - $\mathbb{Z} /n\mathbb{Z}$ - by the following rules:

  • $[a]_n + [b]_n = [a+b]_n$
  • $[a]_n \cdot [b]_n = [a\cdot b]_n$

These are well-defined operations, by the previous theorem.

2.2.2Properties of these operations on congruence

2.2.2.1Addition
  • For any element $[a]$, there is a neutral element, $[0]_n = \{0, n, 2n, \ldots \}$, such that $[0] + [a] = [a]$.
  • For any element $[a]$, there is an additive inverse $-[a]$, such that $[a] + (-[a]) = [0]$. $-[a]$ is equivalent to $[n-a]$: $[a] + [n-a] = [n] = [0]$.
  • Associativity: $([a] + [b]) + [c] = [a] + ([b] + [c])$. The proof for this follows easily from the associativity of addition in $\mathbb{Z}$. We can say that $\mathbb{Z}/n\mathbb{Z}$ inherits this property from $\mathbb{Z}$.
  • Commutatitivty: $[a] + [b] = [b] + [a]$
2.2.2.2Multiplication
  • For any element $[a]$, there is a neutral element, $[1]_n = \{1, n + 1, 2n + 1, \ldots \}$, such that $[1] \cdot [a] = [a]$.
  • Associativity: $([a] \cdot [b]) \cdot [c] = [a] \cdot ([b] \cdot [c])$.
  • Commutatitivty: $[a] \cdot [b] = [b] \cdot [a]$
2.2.2.3Distributivity

This property combines addition and multiplication:

$$[a] \cdot ([b] + [c]) = ([a] \cdot [b]) + ([a] \cdot [c])$$

3Ring structure

$\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$ are instances of what we call a commutative ring, which is defined as a set $R$ together with two binary operations, $+ : R \times R \to R$, and $\times: R \times R \to R$, satisfying the above properties (neutral element, associativity, and commutativity for $+$ and $\times$; an inverse element for addition; and distributivity).