Congruences

The congruence $a\equivb\hbox{ (mod }n)$ (``$a$ is congruent to $b$ mod $n$'') says that, when divided by $n$, $a$ and $b$ have the same remainder.

$$100\equiv34\hbox{ (mod }11)\qquad-6\equiv2\hbox{ (mod }8)$$

In the second congruence, we are using $-6=8(-1)+2$. We always have $a\equivb\hbox{ (mod }n)$ for some $0\le b\le n-1$, and we are usually concerned with that $b$. If $a\equivb\hbox{ (mod }n)$ and $c\equiv d$, we can add or multiply

$$a+c\equivb+d\hbox{ (mod }n)\qquad ac\equivbd\hbox{ (mod }n)$$

Division does not always work: $6\equiv18\hbox{ (mod }12)$, but $3\not\equiv9$.