Modular Arithmetic

Let \(n\) be a positive integer. We denote the set \([0..n-1]\) by \(\mathbb{Z}_n\).

We consider two integers \(x, y\) to be the same if \(x\) and \(y\) differ by a multiple of \(n\), and we write this as \(x = y \pmod{n}\), and say that \(x\) and \(y\) are congruent modulo \(n\). We may omit \(\pmod{n}\) when it is clear from context. Every integer \(x\) is congruent to some \(y\) in \(\mathbb{Z}_n\). When we add or subtract multiples of \(n\) from an integer \(x\) to reach some \(y \in \mathbb{Z}_n\), we say are reducing \(x\) modulo \(n\), and \(y\) is the residue.

We could have chosen different sets for \(\mathbb{Z}_n\), e.g. we could add \(n\) to every member, but our default will be \([0..n-1]\). The elements in this particular representation of \(\mathbb{Z}_n\) are called the least residues.

Example: \(38 = 3 \pmod{5}\) since \(38 = 7\times 5 + 3\). \(-3 = 11 \pmod{14}\) since \(-3 = (-1)\times 14 + 11\).

What is the most natural way of doing arithmetic in \(\mathbb{Z}_n\)? Given two elements \(x, y \in \mathbb{Z}_n\), we can add, subtract or multiply them as integers, and then the result will be congruent to one of the elements in \(\mathbb{Z}_n\).

Example: \(6 + 7 = 1 \pmod{12}\), \(3 \times 20 = 10 \pmod{50}\), \(12 - 14 = 16 \pmod{18}\).

These operations behave similarly to their mundane counterparts. However, there is no notion of size. Saying \(0 < 4 \pmod{8}\) is nonsense for example, because if we add \(4\) to both sides we find \(4 < 0 \pmod{8}\). The regular integers are visualized as lying on a number line, where integers to the left are smaller than integers on the right. Integers modulo \(n\) however are visualized as lying on a circle (e.g. think of a clock when working modulo \(12\)).

Division

Division is notably absent from the above discussion. If \(y\) divides \(x\) as integers, then one might guess we could use the usual definition. Let us see where this leads: we have \(10 = 4 \pmod{6}\). Dividing both sides by \(2\) gives the incorrect equation \(5 = 2 \pmod{6}\).

Thus we have to change what division means. Intuitively, division should "undo multiplication", that is to divide \(x\) by \(y\) means to find a number \(z\) such that \(y\) times \(z\) is \(x\). The problem above is that there are different candidates for \(z\): in \(\mathbb{Z}_6\) both 5 and 2 give 4 when multiplied by 2.

Which answer should we choose for "\(4 / 2\)", \(5\) or \(2\)? We could introduce some arbitrary convention, such as choosing the smallest answer when considering the least residue as an integer, but then division will behave strangely.

Instead, we require uniqueness, that is \(x\) divided by \(y\) modulo \(n\) is only defined when there is a unique \(z \in \mathbb{Z}_n\) such that \(x = y z\).

We can obtain a condition on \(y\) as follows. Suppose \(z_1 y = z_2 y \pmod {n}\). Then by definition, this means for some \(k\) we have \(y(z_1 - z_2) = k n\). Let \(d\) be the greatest common divisor of \(n\) and \(y\). Then \(n/d\) divides \(z_1 - z_2\) since it cannot divide \(y\), thus we have

\[ z_1 y = z_2 y \pmod {n} \]

if and only if

\[ z_1 = z_2 \pmod {n/d} . \]

Thus a unique \(z\) exists modulo \(n\) only if the greatest common divisor of \(y\) and \(n\) is 1.

Inverses

We shall see that a unique \(z\) exists if and only if it is possible to find a \(w \in \mathbb{Z}_n\) such that \(y w = 1 \pmod {n}\). If such a \(w\) exists, it must be unique: suppose \(y w'\) is also 1. Then multiplying both sides of \(y w = y w'\) by \(w\) gives \(w y w = w y w'\), which implies \(w = w'\) since \(w y = 1\). When it exists, we call this unique \(w\) the inverse of \(y\) and denote it by \(y^{-1}\).

How do we know if \(y^{-1}\) exists, and if it does, how do we find it? Since there are only \(n\) elements in \(\mathbb{Z}_n\), we can multiply each element in turn by \(y\) and see if we get 1. If none of them work then we know \(y\) does not have an inverse. In some sense, modular arithmetic is easier than integer arithmetic because there are only finitely many elements, so to find a solution to a problem you can always try every possbility.

We now have a good definition for division: \(x\) divided by \(y\) is \(x\) multiplied by \(y^{-1}\) if the inverse of \(y\) exists, otherwise the answer is undefined.

To avoid confusion with integer division, many authors avoid the \(/\) symbol completely in modulo arithmetic and if they need to divide \(x\) by \(y\), they write \(x y^{-1}\). Also some approaches to number theory start with inversion, and define division using inversion without discussing how it relates to integer division, which is another reason \(/\) is often avoided. We will follow convention, and reserve the \(/\) symbol for integer division.

Example: \(2\times 3+4(5^{-1}) = 2 \pmod{6}\).


Ben Lynn blynn@cs.stanford.edu 💡