next up previous contents
Next: The Greatest Common Divisor Up: Introduction to Number Theory Previous: Introduction to Number Theory   Contents


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.

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

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

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

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

Translated from LaTeX by Scott Sutherland