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}$.