# 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$$. The $$\mod{n}$$ is sometimes omitted when it is clear from the context. Every integer $$x$$ is the congruent 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.

There are different sets we could have chosen 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 \lt 4 \pmod{8}$$ is nonsense for example, because if we add $$4$$ to both sides we find $$4 \lt 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$$? With real numbers, although there are always two square roots of a positive real, we can still define the square root symbol because we stipulate that it refers to the positive square root. But without a notion of size, we cannot say something like “choose the smallest answer”. There are ways of picking a unique answer (e.g. we can choose the smallest answer when considering the least residue as an integer), but then division will behave strangely.

Hence 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 artihmetic 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 💡