Residue Class

algebra

Residue Class

A residue class is an equivalence class of a class representant $a\in \mathbb{Z}$ for a given module $m\in \mathbb{Z}$:

$${\bar{a}}_m=a+m\mathbb{Z}=\{\dots ,a-2m,a-1m,a+0m,a+1m,a+2m,\dots \}$$

Closed Operations

Let $a,b,c,d\in \mathbb{Z}$:

$$a+b\equiv c\mathrm{mod}m\wedge b\equiv d⟹a+d\equiv c\mathrm{mod}m$$ $$a\cdot b\equiv c\mathrm{mod}m\wedge b\equiv d⟹a\cdot d\equiv c\mathrm{mod}m$$

Example: Let $n=(a_1{a}_2\dots a_k{)}_{10}\in \mathbb{Z}$, proof that

$$3\mid \sum _{i=1}^k{a}_i\cdot 10^{i-1}⟹3\mid n\left[⟺3\mid a_1{a}_2\dots a_k\right]$$

Proof:

$$\begin{array}{rl}3\mid \sum _{i=1}^k{a}_i\cdot 10^{i-1}& ⟹\sum _{i=1}^k{a}_i\cdot 10^{i-1}\equiv 0\mathrm{mod}3\\ & \\ 10& \equiv 1\mathrm{mod}3\\ & ⟹\text{10 substitutable with 1 (same residue class)}\\ & \\ & ⟹\sum _{i=1}^k{a}_i\cdot 1^{i-1}\equiv 0\mathrm{mod}3\\ & ⟹\sum _{i=1}^k{a}_i\equiv 0\mathrm{mod}3\\ & ⟹3\mid \sum _{i=1}^k{a}_i\end{array}$$