Modular Arithmetic

Modular arithmetic replaces an integer $a$ by the remainder $b$ it leaves on division by a fixed modulus $n>1$, written $a\equiv b\pmod n$ ("$a$ is congruent to $b$ modulo $n$").

Definition (congruence). $a\equiv b\pmod n$ means $a-b=nk$ for some integer $k$, where $b$ is the least non-negative remainder ($0\le b\le n-1$) when $a$ is divided by $n$. Examples: $25\equiv4\pmod7$ (since $25-4=21=7\times3$), $-20\equiv1\pmod3$, $15\equiv0\pmod5$.

Residue classes. Dividing the integers by $n$ sorts every integer into exactly one of $n$ classes $[0],[1],\ldots,[n-1]$. For $n=5$: $[0]=\{\ldots,-10,-5,0,5,10,\ldots\}$, $[1]=\{\ldots,-9,-4,1,6,11,\ldots\}$, $[2]=\{\ldots,-8,-3,2,7,12,\ldots\}$, $[3]=\{\ldots,-7,-2,3,8,13,\ldots\}$, $[4]=\{\ldots,-6,-1,4,9,14,\ldots\}$; any two numbers in the same class are congruent modulo $5$. This is written $\mathbb Z_5=\{[0],[1],[2],[3],[4]\}$.

A real application: ISBN check digits. Before 2007, the 10-digit ISBN used modulo-$11$ arithmetic for its final check digit (drawn from $\{0,1,\ldots,9,X\}$, $X$ standing for $10$): weighting the first nine digits by $1,2,\ldots,9$, summing, and reducing mod $11$ gives the check digit -- e.g. for $81\text{-}7808\text{-}755\text{-}3$, the weighted sum $1(8)+2(1)+3(7)+4(8)+5(0)+6(8)+7(7)+8(5)+9(5)=245\equiv3\pmod{11}$, matching the printed check digit $3$. Since 2007, the 13-digit ISBN uses modulo-$10$ arithmetic instead: the first 12 digits are weighted alternately $3,1,3,1,\ldots$ from the right, summed, rounded up to the next multiple of $10$, and the difference (the additive inverse mod $10$ of the sum) becomes the 13th digit -- e.g. for $978\text{-}81\text{-}931995\text{-}6$, the weighted sum is $155$, the next multiple of $10$ is $160$, and $160-155=5$ is indeed the printed 13th digit.

Two new binary operations on $\mathbb Z_n=\{0,1,\ldots,n-1\}$.

Definition 12.6. For $a,b\in\mathbb Z_n$:

1. Addition modulo $n$: $a+_nb$ = the remainder of $a+b$ on division by $n$.
2. Multiplication modulo $n$: $a\times_nb$ = the remainder of $a\times b$ on division by $n$. Worked pattern -- $+_5$ on $\mathbb Z_5$. The Cayley table for $+_5$: