congruence

Congruence

$m\in \mathbb{N},m\ge 1$ call it modulus (german: Modul)
$a,b\in \mathbb{Z}:a\equiv b\mathrm{mod}m:\iff m\mid b-a$ ($\iff b-a=km$ for some $k\in \mathbb{Z}$)
In words: $a$ is congruent to $b$ modulo $m$ if $m$ divides the difference of $a$ and $b$, i.e. their difference is an integer multiple of $m$.

Examples

$4\equiv 0\mathrm{mod}2$ (4/2 = 2, 0 remainder)
$14\equiv 24\mathrm{mod}2$, $17\equiv 35\mathrm{mod}3$
$22\not\equiv 60\mathrm{mod}4$

Usage example:

congruence class

residue / congruence class

$$\bar{a}:=a+m\mathbb{Z}$$

The congruence class of $a\mathrm{mod}m$ is an equivalence class.
${\mathbb{Z}}_m=\{\bar{0},\bar{1},\dots ,\overline{m-1}\}$ is the set of all rest classes (factor group).
E.g. for $m=2$:
$\bar{0}=0+2\mathbb{Z}$ → the set of even numbers.
$\bar{1}=1+2\mathbb{Z}$ → the set of odd numbers.
$\bar{2}=\bar{0},\bar{3}=\bar{1},\dots$
So basically, $\bar{0}$ is the set of all numbers that are divisible by $m$, and $\bar{1}$ is the set of all numbers that have a remainder of 1 when divided by $m$ etc.

$m\ge 0⟹\exists m\text{ rest classes}:\bar{0},\dots \overline{m-1}$

Proof:
$n\in \mathbb{Z},\exists q,r:n=mq+r,0\le r<m$ (division with remainder)
$n-r=mq\iff m\mid n-r\iff n\equiv r\mathrm{mod}m$
$⟹\forall n\in \mathbb{Z},\exists 0\le r\le m-1:n\equiv r\mathrm{mod}m\iff \bar{n}=\bar{r}$
In words: any integer $n$ divided by $m$ is congruent to the remainder $r\mathrm{mod}m$. The rest class $\bar{r}$ is the rest class of $n$.

$a,v\in \mathbb{Z}⟹\bar{a}=\bar{b}\vee \bar{a}\cap \bar{b}=\varnothing$

In words: two rest classes are either identical or have nothing in common (“disjoint”; no element of $\bar{a}$ is in $\bar{b}$; $\varnothing$ = empty set).
Proof:
Assumption: $\exists x\in \bar{a}\cap \bar{b}⟹m\mid x-a\wedge m\mid x-b$ (see the definition of rest class above, then the implication is apparent)
$⟹\exists k,l\in \mathbb{Z}:x-a=km,x-b=lm$ (just rewrite with definition of divisibility)
$b-a=x-a-(x-b)=(k-l)m⟹\underline{m\mid b-a}$
WLOG: $\underline{0\le \boxed{a<b}\le m-1<m}⟹\boxed{a=b}$ (the underlined things lead to the implication, the boxed thing is a contradiction)

Operations in ${\mathbb{Z}}_m$ Let $a\equiv c\mathrm{mod}m,b\equiv d\mathrm{mod}m$ We can translate these two congruences to: $\exists q_1,q_2\in \mathbb{Z}:c=a+q_{1}m,d=b+q_{1}m$ → We can add/sub and the congruence stays: $c\pm d=a\pm b+(q_1\pm q_2)m⟹a\pm b\equiv c\pm d\mathrm{mod}m$ → Same for multiplication: $\underline{c\cdot d}=(a+q_{1}m)\cdot (b+q_{2}m)=\underline{ab}+(a{q}_2+b{q}_1+q_1{q}_{2}m)\underline{m}⟹ab\equiv cd\mathrm{mod}m$ ($cd$ differs from $ab$ by a multiple of $m$ → definition of congruence)

$m=2$

Some congruences:
$5\equiv 11\mathrm{mod}2$, (odd, i.e. in $\bar{1}$)
$6\equiv 20\mathrm{mod}2$ (even, i.e. in $\bar{0}$)
→
$11+20\equiv 5+6\mathrm{mod}2$ (still odd)
$11\cdot 20\equiv 5\cdot 6\mathrm{mod}2$ (still even)
Note: $x,y\in \bar{a}⟹x\equiv y\mathrm{mod}m$, i.e. the congruence is still true.

Here’s why we can do this:

$(\tilde{a}\circ \tilde{b})\circ N=(a\circ b)\circ NN⊴(G,\circ )$ … generalizing modulo arithmetic …

Different representations of the same coset/element in the factor group.

For the abelian group $(\mathbb{Z},+)$ and $m\ge 1$, its $m$ cosets area normal subgroup $m\mathbb{Z}⊴\mathbb{Z}$.
Looking at the concrete case of ${\mathbb{Z}}_4$, we have the following congruence classes:
$0+4\mathbb{Z}=\bar{0}=4\mathbb{Z}$ (note: $\bar{0}$ is the neutral element of the factor group)
$1+4\mathbb{Z}=\bar{1}$
$2+4\mathbb{Z}=\bar{2}$
$3+4\mathbb{Z}=\bar{3}$
We can do arithmetic with these classes, e.g.: $(1+4\mathbb{Z})+(2+4\mathbb{Z})=3+4\mathbb{Z}$
This is the same as the addition in ${\mathbb{Z}}_4$, adding the elements and taking the remainder modulo 4.
Same as above, but a different representation: $(17+4\mathbb{Z})+(38+4\mathbb{Z})=55+4\mathbb{Z}$
The reason we can do this is because $4\mathbb{Z}⊴\mathbb{Z}$.

---

For any group $(G,\circ )$ with a normal subgroup $N⊴G$ and the coses $a\circ N,a\in G$ (left and right coset equiv).
Now (like above) we define the same operation on the cosets as on the group, i.e. $(a\circ N)\circ (b\circ N)=(a\circ b)\circ N$
We can now take this concept of modulo arithmetic and generalize it it to any group with a normal subgroup.
$\tilde{a}\in a\circ N=\tilde{a}\circ N$, $\tilde{b}\in b\circ N=\tilde{b}\circ N$
$(\tilde{a}\circ N)\circ (\tilde{b}\circ N)=(a\circ b)\circ N$

---

Proof: $(\tilde{a}\circ \tilde{b})\circ N=(a\circ b)\circ N$
$\exists n_1,n_2,n_3,n_4\in N:$
$\tilde{a}=a\circ n_1=n_2\circ a$ ($n_1,n_2$ are representatives of the same coset)
$\tilde{b}=b\circ n_3=n_4\circ b$
$\tilde{a}\circ \tilde{b}=a\circ n_1\circ b\circ n_3=\underset{u\in N\circ (a\circ b)=(a\circ b)\circ N}{\underbrace{n_2\circ a\circ b}}\circ n_3=\dots$
$(⟹\exists n_5\in N:u=a\circ b=n_5)$
$\cdots =a\circ b\circ n_5\circ n_3\in (a\circ b)\circ N$ (since $n_5\circ n_3\in N$ and $N$ being a subgroup and hence closed).
$⟹(\tilde{a}\circ \tilde{b})\circ N=(a\circ b)\circ N$ $✓$

Link to original

$m=3⟹10\equiv 1\mathrm{mod}3$

From the operation rules earlier: $a=b=10,c=d=1$
$⟹10\cdot 10\equiv 1\cdot 1\equiv 1\mathrm{mod}3⟹10^3\equiv 1\mathrm{mod}3$
$⋮$ (one can proove by induction)
$\forall n\in \mathbb{N}:10^n\equiv 1\mathrm{mod}3$
$n\in \mathbb{N},n=(c_k{c}_{k-1}\dots c_0{)}_{10}$ (n as a decimal number)
$n={\sum }_{i=0}^k{c}_i\cdot 10^i$
$n\equiv \underset{\text{digit sum of }n}{\underbrace{c_k+c_{k-1}+\cdots +c_1+c_0}}\mathrm{mod}3$
$n\equiv 0\mathrm{mod}3\iff \text{digit sum of }n\equiv 0\mathrm{mod}3$
In words: a number is divisible by 3 if the sum of its digits is divisible by 3.
The same works for $9$ too.

$\bar{a}=\bar{c},\bar{b}=\bar{d}$

$⟹\overline{a+b}=\overline{c+d},\overline{a\cdot b}=\overline{c\cdot d}$
→ $\bar{a}+\bar{b}:=\overline{a+b},\bar{a}\cdot \bar{b}:=\overline{a\cdot b}$ (we can directly operate on the rest classes)
E.g. $\bar{0}+\bar{0}=\bar{0}$, $\bar{1}+\bar{0}=\bar{1}$ (even + even = even, odd + even = odd)

$m=3,{\mathbb{Z}}_3=\{\bar{0},\bar{1},\bar{2}\}$

Operation table (always read row $\oplus$ column) for addition:

$$\begin{array}{cccc}+& \bar{0}& \bar{1}& \bar{2}\\ \bar{0}& \bar{0}& \bar{1}& \bar{2}\\ \bar{1}& \bar{1}& \bar{2}& \bar{0}\\ \bar{2}& \bar{2}& \bar{0}& \bar{1}\end{array}$$

Operation table for multiplication:

$$\begin{array}{cccc}\cdot & \bar{0}& \bar{1}& \bar{2}\\ \bar{0}& \bar{0}& \bar{0}& \bar{0}\\ \bar{1}& \bar{0}& \bar{1}& \bar{2}\\ \bar{2}& \bar{0}& \bar{2}& \bar{1}\end{array}$$

Properties of ${\mathbb{Z}}_m$

commutative, associativity, distributive property hold for the operations in ${\mathbb{Z}}_m$.
There is also a neutral element: $\bar{0}$ for addition, $\bar{1}$ for multiplication.
$\forall \bar{a}\in {\mathbb{Z}}_m,\exists \bar{b}\in {\mathbb{Z}}_m:\bar{a}+\bar{b}=\bar{0}$ ($-\bar{a}+\bar{a}=\bar{0}$; elements are invertible – already present in the operation table, just represented without a minus.)
$\forall \bar{a}\in {\mathbb{Z}}_m,\exists \bar{b}\in {\mathbb{Z}}_m:\bar{a}\cdot \bar{b}=\bar{1}$ wrong (not all elements are invertible for multiplication; no division by zero)
Example: Multiplication table for ${\mathbb{Z}}_4$: (see that $\bar{2}$ is not invertible)

$$\begin{array}{ccccc}\cdot & \bar{0}& \bar{1}& \bar{2}& \bar{3}\\ \bar{0}& \bar{0}& \bar{0}& \bar{0}& \bar{0}\\ \bar{1}& \bar{0}& \bar{1}& \bar{2}& \bar{3}\\ \bar{2}& \bar{0}& \bar{2}& \bar{0}& \bar{2}\\ \bar{3}& \bar{0}& \bar{3}& \bar{2}& \bar{1}\end{array}$$

$\bar{a}\in {\mathbb{Z}}_m:\exists {\bar{a}}^{-1},\text{i.e.}{\bar{a}}^{-1}\bar{a}=\bar{a}{\bar{a}}^{-1}=\bar{1}\iff \gcd (a,m)=1$

In words: $\bar{a}$ is invertible in ${\mathbb{Z}}_m$ if and only if $a$ and $m$ are coprime.
Proof:
“$⟹$” $\exists \bar{b}:\bar{a}\bar{b}=\bar{1}$ (assumption; going left to right)
$\iff ab\equiv 1\mathrm{mod}m\iff \exists q\in \mathbb{Z}:ab=1+mq$ ($a$ and $b$ only differ by a multiple of $m$ … $q$)
$t\mid a,t\mid m⟹t\mid ab-1⟹t\mid 1⟹\gcd (a,m)=1$
“$⟸$” $\gcd (a,m)=1⟹\exists e,f\in \mathbb{Z}:ae+mf=1$
$⟹ae=1+(-f)m⟹ae\equiv 1\mathrm{mod}m\equiv \bar{a}\bar{e}=\bar{1}⟹\bar{e}={\bar{a}}^{-1}$
E.g. Find ${\overline{15}}^{-1}\in \mathbb{Z}$
$17=15\cdot 1+2$
$15=2\cdot 5+\boxed{1}$
$7=1\cdot 7+0$
→ $1=15-2\cdot 7=15-(17-15)\cdot 7=-17\cdot 7+8\cdot 15⟹{\overline{15}}^{-1}=\bar{8}\in {\mathbb{Z}}_{17}$

Division and divisibility

$ac\equiv bc\mathrm{mod}m,\gcd (c,m)=1\iff \exists {\bar{c}}^{-1}$
Since $c$ and $m$ are coprime, we can divide by $c$, aka multiply by ${\bar{c}}^{-1}$:
$⟹\bar{a}\cancel{\bar{c}}=\bar{b}\cancel{\bar{c}}⟹a\equiv b\mathrm{mod}m$
If we have:
$ac\equiv bc\mathrm{mod}m,m=\tilde{m}c$
We can’t divide by $c$, because the modul contains it, they are not coprime, there is no inverse.
However, if $\exists k:ac=bc+k\tilde{m}c$
$⟹a=b+k\tilde{m}$
$⟹a\equiv b\mathrm{mod}\tilde{m}$
In words: If there is a common divisor on the left side, the right side, and in the modulo, we can cancel it out / divide by it.

$p\in \mathbb{P},{\mathbb{Z}}_p:\bar{1},\bar{2},\dots ,\overline{p-1}\text{ have a multiplicative inverse}$
In words: All rest classes with a prime modulus (except for $\bar{0}$) have a multiplicative inverse.

ISBN

$a_1{a}_2{a}_3\dots a_9{a}_{10}$ (since there are no $\cdot$, it’s a concatenation of digits, “multiplikation im Monoid der Strings”)
$\forall i:1\le i\le 9,0\le a_i\le 9$
Prüfziffer (check digit): $a_{10}\in \{0,1,2,\dots 9,X\}$
$10a_1+9a_2+\cdots +2a_9+a_{10}\equiv 0\mathrm{mod}11$ ($X$ is treated as $10$)

Theorem: Single errors and transpositions of two digits can be detected (but not corrected).

Proof for single errors:
Let’s assume there is some error at position $1\le i\le 10$:
$c_1=a_1\dots a_i\dots a_{10}$, $a_i=a$
$c_2=a_1\dots \underset{\text{pos }i}{b}\dots a_{10}$, $b\ne a$
We check whether the sum is congruent modulo $11$ for the original and the changed number:
$s={\sum }_{j=1,j\ne i}^{10}(11-j)a_j⟹(\cancel{11-}i)a+\cancel{s}\equiv (\cancel{11-}i)b+\cancel{s}\mathrm{mod}11⟹ia\equiv ib\mathrm{mod}11$
Since all possible $i$ are coprime and thus invertible modulo $11$, we can divide by $i$:
$a\equiv b\mathrm{mod}11,0\le a,b\le 9⟹a=b$
Since $a,b$ are less than the modulo, they have to be equal, else the congruence would not hold.

Proof for single transpositions:
$a⟷a$ (transposition of two digits):
$c_1=a_1\dots a_i{a}_j\dots a_{10}$, $a_i=b,a_j=a$
$c_2=a_1\dots a_j{a}_i\dots a_{10}$
$s={\sum }_{l=1,l\ne i,l\ne j}^{10}(1-l)a_l$
$\cancel{s}+(\cancel{11-}i)a+(\cancel{11}-j)b\equiv \cancel{s}+(\cancel{11-}i)b+(\cancel{11-}j)a\mathrm{mod}11$
$ia+jb\equiv ib+ja$
$(i-j)(a-b)\equiv 0\mathrm{mod}11$
$-9\le i\le 9,i-j\ne 0$
$a\equiv b\mathrm{mod}11⟹a=b$ (same reason as before)
→ The code can only be correct if the sum is congruent modulo $11$.

Link to original