Modular Arithmetic - SS1 Mathematics Lesson Note

Modular arithmetic involves mathematical situations where cyclical or repeating patterns occur. Mathematically, it restricts the number of digits that can be utilized in its operations. For example, \(mod\ 4\) (short for modulus or modulo 4) is a mathematical system where only digits \(0,\ 1,\ 2\ and\ 3\) are available to work with. Likewise, \(mod\ 8\) restricts us to just digits \(0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6\ and\ 7\); and \(mod\ 13\) to digits \(0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10,\ 11\ and\ 12\). It is useful is certain real-life situations such as computer science.

Generally, \(a = b\ (mod\ n)\) where \(a\ \)and \(b\) have the same remainder when divided by \(n\) or equivalently the difference between \(a\) and \(b\) is divisible by \(n\). Consider the numbers below:

Mod 4 Numbers	\[0\]	\[1\]	\[2\]	\[3\]	\[0\]	\[1\]	\[2\]	\[3\]	\[0\]	\[1\]	\[2\]	\[3\]	\[0\]	\[1\]	\[2\]	\[3\]
Natural Numbers	\[0\]	\[1\]	\[2\]	\[3\]	\[4\]	\[5\]	\[6\]	\[7\]	\[8\]	\[9\]	\[10\]	\[11\]	\[12\]	\[13\]	\[14\]	\[15\]

From the table above, in \(mod\ 4:\ 0,\ 4,\ 8\ \)and\(\ 12\) are said to be congruent or equivalent or correspond to each other, meaning they are the same value in the \(mod\ 4\) counting system. Likewise, \(2,\ 6,\ 10\ \)and\(\ 14\) are equivalent to each other in \(mod\ 4\). Viewed this way, it becomes ever clearer:

\(0 \equiv 0(mod\ 4)\) \(1 \equiv 1(mod\ 4)\) \(2 \equiv 2(mod\ 4)\) \(3 \equiv 3(mod\ 4)\)

\(4\ \equiv 0(mod\ 4)\) \(5 \equiv 1(mod\ 4)\) \(6 \equiv 2(mod\ 4)\) \(7 \equiv 3(mod\ 4)\)

\(8\ \equiv 0(mod\ 4)\) \(9 \equiv 1(mod\ 4)\) \(10 \equiv 2(mod\ 4)\) \(11 \equiv 3(mod\ 4)\)

\(12\ \equiv 0(mod\ 4)\) \(13 \equiv 1(mod\ 4)\) \(14 \equiv 2(mod\ 4)\) \(15 \equiv 3(mod\ 4)\)

The ‘\(\equiv\)’ symbol denotes equivalence. So, the natural number \(14\) is equivalent to \(2\) in \(mod\ 4\) because \(\frac{14}{4} = \ 3\ remainder\ \mathbf{2}\ \)and \(7\) is equivalent to \(3\) in \(mod\ 4\) because \(\frac{7}{4} = 1\ remainder\ \mathbf{3}\). We focus on the remainder in modular arithmetic.

This pattern also repeats across the negative side of the real numbers,

Mod 4 Numbers	1	2	3	\[0\]	\[1\]	\[2\]	\[3\]	\[0\]	\[1\]	\[2\]	\[3\]	\[0\]	\[1\]	\[2\]	\[3\]	\[0\]
Natural Numbers	\[- 15\]	\[- 14\]	\[- 13\]	\[- 12\]	\[- 11\]	\[- 10\]	\[- 9\]	\[- 8\]	\[- 7\]	\[- 6\]	\[- 5\]	\[- 4\]	\[- 3\]	\[- 2\]	\[- 1\]	\[0\]