Residue Classes

This refers to sets, that hold all numbers, which have the same residue [math-modulo|modulo] n.

TODO: Put this in it's own note.

Congruence (Modulo): When we write a \equiv_n b (or a \equiv b \pmod{n}), we mean that a and b have the same remainder when divided by n. Equivalently, n divides the difference (a-b).

Let n \in \mathbb{N}^{+} and a\in{0,...,n-1}, then we define the residual class for a \mod n as follows:

a_{n} = \{ z \in \mathbb{Z} | z \mod n = a \mod n \}

Example: 2_{5} = \{ \dots, -8, -3, 2, 7, 12, \dots \}

Quotient Rings

Let n \in \mathbb{N}^{+}, then is \mathbb{Z} \div n \mathbb{Z}=Z_{n} the Quotient Ring of modulo n and the following holds:

\mathbb{Z}_{n} = \{0, 1, 2 \dots n-1\}

Example:

\begin{align} 0_{5} &= \{ \ldots, -10, -5, 0, 5, 10, \ldots \} \\ 1_{5} &= \{ \ldots, -9, -4, 1, 6, 11, \ldots \} \\ 2_{5} &= \{ \ldots, -8, -3, 2, 7, 12, \ldots \} \\ 3_{5} &= \{ \ldots, -7, -2, 3, 8, 13, \ldots \} \\ 4_{5} &= \{ \ldots, -6, -1, 4, 9, 14, \ldots \} \end{align}

Calculation rule:

\begin{align} &\text{1. }(a+b) \bmod n = \left( (a \bmod n) + (b \bmod n)\right) \bmod n \\ &\text{2. }(a-b) \bmod n = \left( (a \bmod n) - (b \bmod n)\right) \bmod n \\ &\text{3. } (a\cdot b) \bmod n = \left((a \bmod n) \cdot (b \bmod n)\right) \bmod n \\ &\text{4. } a^d \bmod n = (a^{d-x} \cdot a^x) \bmod n = ((a^{d-x} \bmod n) \cdot (a^x \bmod n)) \bmod n \; (\text{for } x \leq d) \end{align}