Section8.1The integers modulo \(n\)

It is time for us to finally define what we have been working with for quite a while now.

Definition8.1.1Integers Modulo \(n\)
For a positive integer \(n\), the set of equivalence classes of integers modulo \(n\) is called the integers modulo \(n\). We denote it \(\mathbb{Z}_n\). That is, \[\mathbb{Z}_n = \{[0],[1],[2],\cdots,[n-2],[n-1]\}\; .\] In the case where \(n=p\) is a prime, we usually write \(\mathbb{Z}_p\).

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.

As a first step in visualizing, we can make an addition table. This is not very interesting. But in some sense, it is interesting that it isn't interesting. Does that make any sense?

The top row and left column may be considered as a list of \(a\) and \(b\). Any ideas about patterns here?

It's also possible to make a multiplication table. This makes things a little more interesting.

Again, notice that the columns and rows are both from 0 to \(n-1\); this is standard. For now we'll usually just use the set of least nonnegative residues to represent \(\mathbb{Z}_n\) - that is, \(\{[0],[1],[2],\ldots,[n-2],[n-1]\}\).

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.1

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); it is so cool that even my wife says, “What's that — it's neat!”

The \(a\) row and \(b\) column give the color corresponding to \(a\cdot b\text{ mod (}p)\; .\)
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\). Since zero times anything is zero, that gives us a lot of that color along two edges.

Can you see the difference between prime and composite moduli better now?

Subsection8.1.2Inverses

Let's focus on the tables/graphs for when \(n=p\) a prime. There's one interesting observation we can make about them for sure. Every row and every column (other than the ones corresponding to 0) has the entry \(1\) in it. (That's the deepest nonzero blue.) You can't necessarily say this about other numbers. Here's a proof.

  • If \(gcd(a,n)=1\), then \(ax\equiv b\) mod (\(n\)) has a unique solution in \(\mathbb{Z}_n\).
  • So if \(n=p\) is prime, then \(gcd(a,p)=1\) all the time, except for \(a\equiv 0\).
  • So if \(b=1\) then we have a unique solution — for prime moduli, every non-zero element has a unique inverse element in \(\mathbb{Z}_p\).

(This means it is a field - another example of bizarre but fun math nomenclature.)

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\)?