Introduction to Cryptography with Coding Theory, 3rd Edition

3.3 Congruences

One of the most basic and useful notions in number theory is modular arithmetic, or congruences.

Definition

Let $a\text{,}b\text{,}n$ be integers with $n\ne 0\text{.}$ We say that

$$\begin{array}{cc}a\equiv b& \left(\mathrm{mod}n\right)\end{array}$$

(read: $a$ is congruent to $b$ mod $n$) if $a-b$ is a multiple (positive or negative or zero) of $n\text{.}$

Another formulation is that $a\equiv b\left(\mathrm{mod}n\right)$ if $a$ and $b$ differ by a multiple of $n\text{.}$ This can be rewritten as $a=b+nk$ for some integer $k$ (positive or negative).

Example

$$\begin{array}{ccc}\begin{array}{cc}32\equiv 7& \left(\mathrm{mod}5\right)\text{,}\end{array}& \begin{array}{cc}-12\equiv 37& \left(\mathrm{mod}7\right)\text{,}\end{array}& \begin{array}{cc}17\equiv 17& \left(\mathrm{mod}13\right)\text{.}\end{array}\end{array}$$

Note: Many computer programs regard $17\left(\text{mod}10\right)$ as equal to the number 7, namely, the remainder obtained when 17 is divided by 10 (often written as $17\%10=7$). The notion of congruence we use is closely related. We have that two numbers are congruent mod $n$ if they yield ...