Modular Arithmetic

Modular Arithmetic is useful in a variety of contexts and even is a helpful way to think about positional numeral systems (like our base ten system) in which certain placeholders are used. There are many applications in computer programming and cryptography as well as systems of time and date keeping, but we will focus here only on how to compute results. We will restrict ourselves to the integers and also will not delve into details about relations, congruence, etc. Students interested in these detail are referred to the Wikipedia articles of the topics of their interest, as well as any first year undergraduate textbook on discrete math or number theory.

The Division Algorithm

The division algorithm is the familiar procedure from a first introduction to division. When asked to find the quotient (the number of equal bunches of a certain size) when dividing one natural number (the numerator or dividend) by another (the denominator or divisor) we often get a leftover remainder (henceforth called the residue). For instance if we are asked to divide $15\div 4={\frac {14}{4}}$ we have a dividend (numerator) of $14$ and divisor (denominator) of $4$. We rewrite the problem in an equivalent manner $4\cdot 3+2$ and note that the quotient is $3$ and the residue is $2$. In general we can write any integer $a$ (the dividend) as the product of any integer $b$ (the divisor) and some integer $q$ (the quotient) adder to an integer $r$ (the residue). The value of the residue must be between $0$ and $|b|-1$. Where the straight bars represent to absolute value (ie. positive numbers remained unchanged and negative numbers are multiplied by $-1$ to make them positive).

Note the word divisor is often also used as a short hand for a number that divides another with no residue (ie.$7$ divides $56$ with residue $0$). This is different to the sense in which the word is used earlier in this section.

The Integers Modulo $n$

Note: when congruence ($\equiv$) comes up, feel free to treat it as equality ($=$). There is a difference (for instance we will see how $3$ and $9$ can be congruent shortly), but it is not useful to belabour the point for our purposes.

What we mean by the integers modulo $n$ is that we will represent each number by it's residue when it is divided by $n$. So $3\equiv 3{\pmod {6}}$, while $8\equiv 2{\pmod {6}}$. $9\equiv 3{\pmod {6}}$, so we notice that many of our numbers will be mapped to the same place. In fact we only have $n$ numbers left. They are the numbers in the set $\mathbb {Z} _{n}=\{0,1,2,\dots ,n-2,n-1\}$, the integers modulo $n$. In the case of integers modulo $6$ we have $6$ numbers $\mathbb {Z} _{6}=\{0,1,2,3,4,5\}$. Note while the $\mathbb {Z} _{n}$ notation is common, it is not the only notation and is the same notation used for the n-adic integers, so use it with some care.

We will define addition subtraction and multiplication on $\mathbb {Z} _{n}$ as taking elements of $\mathbb {Z} _{n}$ and doing addition, subtraction or multiplication on them as normal, then asking what the result is equal to modulo $n$. We can take the mod after each step (to keep the numbers being crunched small) or we can just do all the computation at once and do one mod at the end (quicker if being done with a calculator). The results will be the same. Note negative answers, must give a positive residue by definition. For example $3-4=-1=-1\cdot 6+5$ so $3-4\equiv 5{\pmod {6}}$

For example $(4+5)\cdot 5\equiv 3\cdot 5\equiv 3{\pmod {6}}$ and $(4+5)\cdot 5=45=6\cdot 7+3$, and $45\equiv 3{\pmod {6}}$ as expected.

Exercises

Try some computations and see if you get the same answer both ways. First do the computation by hand taking the mod at each step, then check by doing all the computations on a calculator and taking the mod at then end. To do the mod quickly on a calculator you can divide by $n$, take the answer and subtract what the answer rounded down is (ie. -6.2-(-7)=0.8) then multiply by $n$. You will get the number you calculated or something close, depending on the accuracy of the device you are using.

For example $-56789\equiv 8{\pmod {13}}$ as $-56789\div 13=-4368.384615\dots$, $-4368.384615\ldots -(-4369)=0.615384615\dots$, and $13\cdot (0.615384615\dots )=8$