Congruences

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

$${100}\equiv{34}\hbox{ (mod }{11})\qquad{-6}\equiv{2}\hbox{ (mod }{8})$$

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

$${a+c}\equiv{b+d}\hbox{ (mod }{n})\qquad {ac}\equiv{bd}\hbox{ (mod }{n})$$

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