Now, armed with our accumulated knowledge on division, divisors, remainders, primes, and sets, we'll define a system of arithmetic on sets of integers based around remainders, which seems like a strange thing to do.
Often times, we want to do calculations based around multiples of certain numbers, like time—we represent time in "chunks". For instance, we group 60 seconds together into a minute, 60 minutes together into an hour, and 24 hours into a day, which we sometimes further split up into chunks of 12. We can conveniently represent these chunks together on one circle.
Modular arithmetic formalizes these notions. One of the things we'll see is that in certain cases, working in these structures gives us a notion of "division" that is well-defined. The system of modular arithmetic was first developed by Gauss.
Let $m$ be an integer. For integers $a$ and $b$, we say that $a$ is congruent to $b$ modulo $m$, written $a \equiv b \pmod m$ or $a \equiv_m b$, if $m \mid a-b$.
This definition looks a bit strange, but it really means that $a$ and $b$ have the same remainders when divided by $m$. (Something you can try to prove)
Ultimately, we want to be able to talk about integers that are equivalent to each other with respect to a particular modulus. An easy example of this is when we think about integers modulo 10, since our entire number system is built around 10s. We can formally define what it means to be "equivalent".
A relation $\sim$ is an equivalence relation if $\sim$ satisfies the following:
Equivalence relations are called as such because they capture relationships that are similar to, but not exactly, equality. For instance, if I have two propositional formulas $\varphi$ and $\neg \neg \varphi$, we can't say they're equal because they aren't: they contain different symbols and one is longer than the other. However, we can say that they're logically equivalent because they mean the same thing (in classical logic). If we really wanted to, we can define the notion of logical equivalence more formally and then show that it satisfies the conditions for equivalence relations.
For $m \gt 0$, $\equiv_m$ is an equivalence relation.
Using the notion of an equivalence relation, we can take all the integers in $\mathbb Z$ and try to group them together so that they contain equivalent members. For instance, if we choose $m = 2$, then all even numbers are equivalent to each other (i.e., $0 \pmod 2$) and all odd numbers are equivalent to each other (i.e., $1 \pmod 2$).
To do this, we will need to introduce the notion of sets. Sets are the fundamental structure in mathematics. For now, we introduce the basic idea and how to describe sets. We will get into more about how to work with sets once we talk about combinatorics.
A set is an unordered collection of objects. If $S$ is a set and $a$ is a member of $S$, then we write $a \in S$, which is read "$a$ is an element of $S$". Similarly, if $a$ is not a member of $S$, then we write $a \not \in S$.
The main question that we consider when working with sets is membership: does a particular item $a$ belong to a set $S$ or not?
We can describe sets by listing the members of the set or by using comprehensions, also called set-builder notation.
If we wanted to define the set of even natural numbers, we can write something like $\{2,4,6,\dots\}$. Using comprehensions, we can also write $$\{n \in \mathbb N \mid \exists m \in \mathbb N, n = 2 \cdot m \},$$ which says that we want the set of all natural numbers $n$ such that $n$ can be expressed as $2 \cdot m$ for some natural number $m$. That, of course, turns out to be the even natural numbers.
This may look kind of similar to Python comprehensions. This is because comprehensions in Python are inspired by set comprehensions.
One thing to be aware of is that descriptions of sets are definitions, not algorithms. It is not necessary for a definition of a set to give you enough information to find members of the set or determine membership. In fact, this is a central fact of computer science: there are sets that cannot be computed.
The sets that we get from collecting integers that are all equivalent to each other modulo $m$ are called equivalence classes.
For all $m \gt 0$ and $a \in \mathbb Z$, we define the equivalence class modulo $m$ of $a$ to be the set of integers $$[a]_m = \{b \in \mathbb Z \mid b \equiv_m a\}.$$
Typically, we refer to equivalence classes by their "obvious" name, which is the member of the class that is between 0 and $m-1$. This is called the canonical representative of the class. Of course, we should keep in mind that $[0] = [m] = [2m] = [-m]$ and such. But in addition to this, sometimes the $[]_m$ gets dropped for convenience's sake and we have to determine from context whether "2" means $2 \in \mathbb Z$ or $[2]_m$. Usually, this becomes clear with the usage of $\pmod m$ and we will try to make that explicit, but outside of this course, that's not always guaranteed.
There is a lot of notation here that means almost the same thing, so let's take a moment to settle it all.
Where are we headed with this? We would like to do arithmetic on these things.
We define operations $\oplus_m$ and $\otimes_m$ on the equivalence classes of $m$ by
All of this seems a bit obvious, but just like we did when we were defining addition on the natural numbers, we should think about what we're really doing here. We've defined operations $+$ and $\cdot$ that look like our usual operations on the integers. However, observe that we're not adding and multiplying integers; we've defined a notion of adding and multiplying sets of integers.
Based solely on this, there is no reason that what we've defined is guaranteed to work. For instance, how do we know that when adding two sets in this way that we even get a set that makes sense at all? So of course, we have to prove this and it will turn out that our definitions of equivalence classes and addition and multiplication on those classes is such that everything works out intuitively almost without a second thought.
We will only show that for $a_1 \equiv a_2 \pmod m$ and $b_1 \equiv b_2 \pmod m$, we have $a_1 + b_1 \equiv a_2 + b_2 \pmod m$. Multiplication is left as an exercise.
By definition, we have that $m \mid a_1 - a_2$ and $m \mid b_1 - b_2$. Then we have $m \mid (a_1 - a_2) + (b_1 - b_2)$. We can easily rearrange this to get $m \mid (a_1 + b_1) - (a_2 + b_2)$ and therefore, $a_1 + b_1 \equiv a_2 + b_2 \pmod m$.
Now, we can define our structure.
Let $\mathbb Z_m = \{[0]_m, [1]_m, \dots, [m-1]_m\}$. The integers mod $m$ is the set $\mathbb Z_m$, together with the binary operations $\oplus_m$ and $\otimes_m$. The integers mod $m$ are denoted by $\mathbb Z/\equiv_m$ or simply as $\mathbb Z_m$.
Notice again that the while the elements of $\mathbb Z$ are numbers, the elements of $\mathbb Z_m$ are sets of integers—specifically equivalence classes.
Up to now, we have been working implicitly in the structure $\mathbb Z$, the integers. As I've briefly alluded to before, we're not only talking about the domain $\mathbb Z$ but also how we interpret operations like $+$ and $\times$. The integers mod $m$, $\mathbb Z_m$, is another structure, whose basic elements are the equivalence classes with respect to $\equiv_m$.
These kinds of structures—a set together with binary operations $+$ and $\cdot$ and identities for both operations—are called rings. Rings can be thought of as being defined by five things:
So the ring of the integers would be $(\mathbb Z, +, \times, 0, 1)$. And the ring of the integers modulo $m$ would be $(\mathbb Z_m, \oplus_m, \otimes_m, [0]_m, [1]_m)$.
The alternative notation $\mathbb Z/\equiv_m$ gives us a hint at what's happening. We took $\mathbb Z$ and partitioned it into equivalence classes by the relation $\equiv_m$. This idea of taking an algebraic structure and constructing another structure based on an equivalence relation is something that comes up a lot in algebra and is called a quotient structure, where quotient in the algebraic context just means equivalence class.
An observation one can make here is that the result of doing this seems to be that all we're doing is taking our numbers and treating them as though they are just the respective remainders. And this is what ends up happening in practice. But there's something subtle going on here, which is that we're really implicitly jumping back and forth between different algebraic structures (the integers, $\mathbb Z$, and the integers modulo $m$, $\mathbb Z_m$).
Let's see how modular arithmetic can be used. Suppose we want to find the remainder of $3^{41}$ when divided by $7$. We know that this is an integer $r$ such that $0 \leq r \lt 7$ and $r \equiv 3^{41} \pmod 7$. This seems daunting at first, but we can use equivalence modulo 7 to help us reduce this integer.
First, we compute some simple powers. We observe that $3^2 \equiv 9 \equiv 2 \pmod 7$ and $3^3 \equiv 27 \equiv -1 \pmod 7$. Using these, we can break up the power in the following way: \[3^{41} \equiv 3^2 \cdot 3^{39} \equiv 3^2 \cdot (3^3)^{13} \equiv 2 \cdot (-1)^{13} \equiv 2 \cdot -1 \equiv -2 \equiv 5 \pmod 7.\]
One can verify this by computer:
>>> divmod(3**41, 7)
(5210428053881540914, 5)
>>> 3**41 == 5210428053881540914 * 7 + 5
TrueI mentioned earlier that one of the things that this structure allows us to do is, under certain conditions, "divide" things in the sense that there is an operation that we can perform on elements of our structure that reverse mulitplication. I say "divide" because the operation that we perform is not really division. It's more accurate to say that we'll be showing that multiplicative inverses exist.
If integers $m \gt 0$ and $a$ are relatively prime, then $a$ has a multiplicative inverse mod $m$. That is, there exists an integer $b$ such that $a \cdot b \equiv 1 \pmod m$.
Consider $\mathbb Z_4$. There are four equivalence classes: $0,1,2,3$. Since 1 and 3 are coprime, they have inverses: $1^{-1} \equiv 1 \pmod 4$ (this is obvious) and $3^{-1} \equiv 3 \pmod 4$, which we get by observing that $3 \cdot 3 \equiv 9 \equiv 1 \pmod 4$ (or $3 \cdot 3 \equiv -1 \cdot -1 \equiv 1 \pmod 4$). However, 2 has no inverse: \begin{align*} 2 \cdot 0 &\equiv 0 &\pmod 4 \\ 2 \cdot 1 &\equiv 2 &\pmod 4 \\ 2 \cdot 2 &\equiv 4 \equiv 0 &\pmod 4 \\ 2 \cdot 3 &\equiv 6 \equiv 2 &\pmod 4 \end{align*}