Theorem A.0.1. The Division Algorithm.
Let \(a\) be an integer and let \(b\) be a positive integer. Then there exist unique integers \(q\) and \(r\) for which
\begin{equation*}
a = qb+r\text{,}
\end{equation*}
and \(0 \le r < b\text{.}\)
Appendix A The Integers Modulo \(n\)
In this short appendix we will define modular arithmetic. There are other books and sources that develop these ideas in a more thorough, formal manner. However, we are primarily aiming for a streamlined approach that will serve our discussion of finite fields in Section 2.1.
The Division Algorithm is essential to what follows.
In this statement of the Division Algorithm, the reader should think of dividing \(a\) by \(b\text{,}\) where \(q\) is the quotient and \(r\) is the remainder. For example,
\begin{equation*}
17 = 5(3) + 2
\end{equation*}
captures the information that dividing \(17\) by \(3\) leaves a remainder of \(2\text{.}\) Similarly, the equation
\begin{equation*}
-10 = -2(7) + 4
\end{equation*}
tells us that dividing \(-10\) by \(7\) gives a remainder of \(4\text{.}\) It is crucial for uniqueness in the Division Algorithm that we insist the remainder \(r\) is in the specified range. (In other words, it is not appropriate to write \(-10=-1(7)+(-3)\) as an application of the Division Algorithm to \(a=-10\) and \(b=7\text{.}\))
The Division Algorithm provides a necessary link between the definition of congruence and what follows.
Definition A.0.2.
Let \(a\) and \(b\) be integers and let \(n\) be a natural number. Then we say that \(a\) and \(b\) are congruent modulo \(n\) if \(n \mid (a-b)\text{.}\) We write this as \(a \equiv b \pmod{n}\text{.}\)
While this is the definition of congruence mod \(n\text{,}\) there is an equivalent way we can understand the meaning of two numbers being congruent in this way.
Proposition A.0.3.
Let \(a\) and \(b\) be integers and let \(n\) be a natural number. Then \(a \equiv b \pmod{n}\) if and only if \(a\) and \(b\) have the same remainder when divided by \(n\text{.}\)
We now define a relation on \(\zz\text{.}\) Let \(n\) be a natural number. If \(a\) and \(b\) are integers, then we say that \(a\) is related to \(b\) when \(a \equiv b \pmod{n}\text{.}\) (Proposition A.0.3 gives the more intuitive way to understand this relation—two integers are related if they have the same remainder when divided by \(n\text{.}\)) It is a good (and not terribly difficult) exercise to show that this is an equivalence relation on \(\zz\text{.}\) For an integer \(m\text{,}\) we will use the notation \([m]\) to denote the equivalence class of \(m\) under this relation.
Definition A.0.4.
Let \(n \in \nn\text{.}\) Then the equivalence classes of the congruence mod \(n\) equivalence relation are \([0], [1], \ldots, [n-1]\text{.}\) The integers modulo \(n\) is the set
\begin{equation*}
\zz_n = \{[0], [1], \ldots, [n-1]\}\text{.}
\end{equation*}
Addition and multiplication can be defined on this set in the following way. For any \([a], [b] \in \zz_n\text{,}\)
\begin{align*}
[a]+[b] \amp :=[a+b]\\
[a]\cdot [b] \amp :=[ab]\text{.}
\end{align*}
It takes a little bit of work (but not too much!) to show that these operations are well-defined.
When performing calculations in \(\zz_n\text{,}\) we will prefer to use one of the numbers \(0, 1, \ldots, n-1\) as the equivalence class representative. For example, though it is correct to write \([5]+[6]=[11]\) in \(\zz_7\text{,}\) we will prefer to write \([5]+[6]=[4]\text{.}\) (Note that knowing the integer \(n\) is essential in these calculations!)
Example A.0.5.
Let’s carry out some basic arithmetic within \(\zz_8\text{.}\)
-
\(\displaystyle [3]+[5]=[0]\)
-
\(\displaystyle [6]+[4]=[2]\)
-
\(\displaystyle [2]\cdot [7]=[6]\)
-
\(\displaystyle [3]\cdot [5] = [7]\)
-
\(\displaystyle [3]([4]+[5]) = [3]\)
At this point the reader may see that, for each \(n \in \nn\text{,}\) \(\zz_n\) is its own mathematical universe, just like \(\zz\) or \(\rr\text{,}\) with its own calculations and quirks. In particular, it is illuminating to think about what properties of addition and multiplication \(\zz_n\) shares with \(\rr\text{.}\) (Also: In which cases does the value of \(n\) affect whether or not these properties hold?)
While the full impact of those questions is best pursued in an abstract algebra class, one question has immediate relevance for our current subject: For which \(n \in \nn\) do all nonzero elements in \(\zz_n\) have multiplicative inverses?
In Example A.0.5 we carried out calculations in \(\zz_8\text{,}\) so let’s examine that set again. Importantly, the element \([1]\) is the multiplicative identity in \(\zz_8\text{,}\) meaning that multiplying each \([m] \in \zz_8\) by \([1]\) leaves \([m]\) unchanged. By multiplying every element in \(\zz_8\) by \([2]\text{,}\) we can see that \([1]\) is never the result. This shows that \([2]\) has no multiplicative inverse in \(\zz_8\text{.}\) Further, it is illuminating to note that the elements \([1]\text{,}\) \([3]\text{,}\) \([5]\text{,}\) and \([7]\) have multiplicative inverses in \(\zz_8\) while the elements \([2]\text{,}\) \([4]\text{,}\) and \([6]\) do not. However, the issue is deeper than the parity of the elements of the equivalence class; the key ingredient is relative primeness with \(n\text{.}\)
We hope this discussion makes the following theorem believable.
Theorem A.0.6.
The set \(\zz_n\) has the property that all nonzero elements have a multiplicative inverse if and only if \(n\) is prime.
In the context of Section 2.1, Theorem A.0.6 leads to the result that \(\zz_n\) is a field if and only if \(n\) is prime. In this case, we will use the notation \(\ff_n\) in place of \(\zz_n\text{.}\) We will also often drop the square-bracket notation and, for example, refer to \(2\) instead of \([2]\) as an element of \(\ff_3\text{.}\)
