Chapter 3 Modular Arithmetic

Reading Materials: Yan, S.Y. Number theory for computing. (Berlin: Springer-Verlag, 2002) 2nd edition. Section 1.2 Theory of divisibility pp.21-pp.24 , Section 1.6 Theory of congruences pp.111-119

3.1 Congruence

Modular arithmetic is a system of arithmetic for integers where the number “wraps around” after reaching a certain value we call modulus

Modular arithmetic is commonly used in number theory, algebra (group theory, ring theory, etc) and also in cryptography. An example in daily life is the clock. The numbers go from 1 to 12, but when you get to “13 o’clock”, it actually becomes 1 o’clock again (think of how the 24 hour clock numbering works). So 13 becomes 1, 14 becomes 2, and so on. This can keep going, so when you get to “25 o’clock’’, you are actually back round to where 1 o’clock is on the clock face (and also where 13 o’clock was too), this is arithmetic modulo 12.

In our clock example, the number go from 1 to 12. In formal mathematics, we usually start from 0. In this case our clock would have 12 replaced with zero. Thus, \[\begin{equation} 24\equiv 0 \mod{12} \end{equation}\] Two integers \(a\) and \(b\) are said to be congruent modulus \(k\) if when they are divided by \(k\), they have the same remainder.

More examples: \[\begin{equation} \begin{split} 3 &\equiv 5 \mod{2} \end{split} \end{equation}\] 3 divided by 2 gives 1 with remainder 1, 5 divided by 2 gives 2 with remainder 1. \[\begin{equation} \begin{split} 14 &\equiv 2 \mod{12} \end{split} \end{equation}\] 14 divided by 12 gives 1 with remainder 2, 2 divided by 12 gives 0 with remainder 2.

How about negative numbers? \(-17 \mod{12}\) for example: \[\begin{equation} \begin{split} -17 \mod{12} & \equiv -5\mod{12}\\ & \equiv 7 \mod{12} \end{split} \end{equation}\]

3.2 Operations in Modular Arithmetics

Examples in modulus 12: \[\begin{equation} \begin{split} 14+28\equiv 2+4 \equiv 6 & \rightarrow 14+28 \equiv 6\mod{12}\\ 28-14\equiv 4-2 \equiv 2 & \rightarrow 28-14 \equiv 2\mod{12}\\ 11+28\equiv 11+4 \equiv 15 \equiv 3 & \rightarrow 11+28 \equiv 3\mod{12}\\ 14\times28\equiv 2\times4 \equiv 8 & \rightarrow 14\times28 \equiv 8\mod{12}\\ \end{split} \end{equation}\] Division can not be straightforwardly extended. For example, \(4\div 12\) is not defined since \(12\equiv 0 \mod 12\). We should first define multiplicative inverse of \(\mod k\).

Multiplicative inverse \(m^{-1}\) of integer \(m\) is defined as: \[\begin{equation} m\times m^{-1} = 1 \mod k \end{equation}\] Then we define \(a\div b\) in \(\mod k\) as multiplication of \(a\times b^{-1}\). For example: \[\begin{equation} \begin{split} 2^{-1} \mod 7 & \\ 2 \times 4 \equiv 1 \mod 7 & \rightarrow 2^{-1} \mod 7 = 4 \mod 7 \end{split} \end{equation}\] Division example: \[\begin{equation} 6 \div 2 \mod 7 \equiv 6 \times 2^{-1} \equiv 6\times 4 \equiv 24 \equiv 3 \mod 7 \end{equation}\] Inverse don’t always exist, for example, the inverse of \(2 \mod 4\).