Residue Classes
\[a\]
is divided by a number \[n\]
the result is a quotient \[q\]
and remainder \[r\]
.\[a=nq+r, 0 \le r \lt n\]
The set of integers
\[0, \; 1, \; 2, ..., n-1\]
form the residue classes of \[a \; (mod \; n)\]
.Addition and multiplication
\[mod \; n\]
is we ll defined, so that\[a \equiv c \; (mod \; n), b \equiv d \; (mod \; n) \rightarrow ac=Bud \; (mod \; n), \; a+c=b+d \; (mod \; n)\]
.Modular arithmetic gives rise to important structures like groups, shown below for addition and multiplication
\[mod \; 5\]
, Additive groups are always possible but multiplication groups are only formed modulus a prime number.\[{}+{}_5\] | 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 2 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
\[{}\times{}_5\] | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 |
| 2 | 2 | 4 | 1 | 3 |
| 3 | 3 | 1 | 4 | 2 |
| 4 | 4 | 3 | 2 | 1 |
