It is time for us to finally define what we have been working with for quite a while now.
Definition8.1.1.Integers Modulo \(n\).
For a positive integer \(n\text{,}\) the set of equivalence classes of integers modulo \(n\) is called the integers modulo \(n\). We denote it \(\mathbb{Z}_n\text{.}\) That is,
In the case where \(n=p\) is a prime, we usually write \(\mathbb{Z}_p\text{.}\) (For those who have had an abstract algebra course, this may be different notation than you have used, but we will consistently use this one.)
This friendly number system will become a good acquaintance, if not friend, throughout the rest of the course. We’ll explore it soon, but first let’s see some of the basic properties.
As it turns out, \(\mathbb{Z}_n\) has several very interesting properties. Like all of our number systems in this class, you can add and multiply elements of \(\mathbb{Z}_n\) (we call something like that a ring). This is true because of our earlier proof of well-definedness for addition and multiplication in Proposition 4.3.2.
As a first step in visualizing, we can make an addition table. (See Figure 8.1.2 or the interact after it.) This is not very interesting. But in some sense, it is interesting that it isn’t interesting. Does that make any sense?
\(+\)
\([0]\)
\([1]\)
\([2]\)
\([0]\)
\([0]\)
\([1]\)
\([2]\)
\([1]\)
\([1]\)
\([2]\)
\([0]\)
\([2]\)
\([2]\)
\([0]\)
\([1]\)
Figure8.1.2.Addition table for \(\mathbb{Z}_3\)
The top row and left column may be considered as a list of \(a\) and \(b\text{.}\) Any ideas about patterns here?
It’s also possible to make a multiplication table. (See Figure 8.1.3 or the interact after it.) This makes things a little more interesting.
\(\times\)
\([0]\)
\([1]\)
\([2]\)
\([0]\)
\([0]\)
\([0]\)
\([0]\)
\([1]\)
\([0]\)
\([1]\)
\([2]\)
\([2]\)
\([0]\)
\([2]\)
\([1]\)
Figure8.1.3.Multiplication table for \(\mathbb{Z}_3\)
Again, notice that the columns and rows are both from \(0\) to \(n-1\text{;}\) this is standard. For now we’ll usually just use the set of least nonnegative residues to represent \(\mathbb{Z}_n\text{;}\) recall that this is \(\{[0],[1],[2],\ldots,[n-2],[n-1]\}\text{.}\)
Are there any patterns you notice here?
There is at least one observation that is curious. For some moduli, the only zeros are where we expect them, in the top row and left column. For others, they are in other spots.
Subsection8.1.2Visualization
What’s even better is to see this visually! I still can’t get over how easy it is for me to do this in Sage (and other math programs), such as in the following graphic and interact. It is so cool that my (non-mathematician) wife says, “What’s that – it’s neat!” I wish more people could experience this joy of beauty in math.
Figure8.1.4.Colored multiplication table for \(n=7\)
How does one interpret this graphic? The \(a\) row and \(b\) column give the color corresponding to \(a\cdot b\text{ (mod }p)\text{.}\) That means the first (\(0\)th) column is the color for \(a\cdot 0=0\) and the second (\(1\)st) column gives the colors of each element \(a\cdot 1=a\) of \(\mathbb{Z}_n\text{.}\) Since zero times anything is zero, that gives us a lot of that color (deep blue in the default) along two edges.
Can you see the difference between prime and composite moduli better now?
Subsection8.1.3Inverses
Let’s focus on the tables/graphs for when \(n=p\) a prime. There’s at least one interesting observation we can make about them. Every row and every column (other than the ones corresponding to 0) has the entry \(1\) in it. (That’s the deepest nonzero blue in the default coloring.)
You can’t necessarily say this about other numbers, so let’s translate this into notation.
Fact8.1.5.
When \(p\) is prime, every nonzero element of \(\mathbb{Z}_p\) has an inverse.
If \(\gcd(a,n)=1\text{,}\) then \(ax\equiv b\) (mod \(n\)) has a unique solution in \(\mathbb{Z}_n\text{.}\) So if \(n=p\) is prime, then \(\gcd(a,p)=1\) always, except for \(a\equiv 0\text{.}\)
Now we let \(b=1\text{,}\) and finding \(x\) becomes the same as finding the inverse number of \(a\) (recall Definition 5.3.4). So for prime moduli, every non-zero element has a unique inverse in \(\mathbb{Z}_p\text{.}\)
(In algebraic nomenclature, this means \(\mathbb{Z}_p\) is a field, yet another example of bizarre but fun math terminology.)
What was the command again to get an inverse?
It turns out there is an even easier way to get at this in Sage than the one I used last time! In retrospect, it makes sense.
Go back to the graphics or tables. Can you “see” that there is (exactly one) inverse for every non-zero element of \(\mathbb{Z}_p\text{?}\)
