Number Theory

Modular Arithmetic

Let $n$ be a positive integer. We denote the set ${0, . . ., n - 1}$ by $ℤ_{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 (mod 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 $ℤ_{n}$ . When we add or subtract multiples of $n$ from an integer $x$ to reach some $y \in Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character 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 Unknown character em Unknown character least residues Unknown character / em Unknown character . Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character Unknown character strong Unknown character Example Unknown character / strong Unknown character :$ 38 = 3 \pmod{5} $since$ 38 = 7\times 5 + 3 $.$ -3 = 11 \pmod{14} $since$ -3 = (-1)\times 14 + 11 $. Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character 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 $. Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character Unknown character strong Unknown character Example Unknown character / strong Unknown character :$ 6 + 7 = 1 \pmod{12} $,$ 3 \times 20 = 10 \pmod{50} $,$ 12 - 14 = 16 \pmod{18} $. Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character 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 $) . Unknown character / p Unknown character Unknown character / div Unknown character Unknown character / div Unknown character Unknown character h 2 id = {Unknown character}_{division} Unknown character Unknown character Division Unknown character / h 2 Unknown character Unknown character div class = Unknown character sectionbody Unknown character Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character 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} $. Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character 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 . Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character 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 . Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character 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 $. Unknown character / p Unknown character Unknown character / div Unknown character Unknown character div class = Unknown character paragraph Unknown character Unknown character Unknown character p Unknown character 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 (mod n)

if and only if

z_{1} = z_{2} (mod 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 ℤ_{n}$ such that $y w = 1 (mod 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 $ℤ_{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 (mod 6)$ .

Bonus Section

Modular Arithmetic

Inverses