NTIC The Integers Modulo $n$

Subsection 8.1.1 Definition

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

Definition 8.1.1. Integers 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 $Z_{n} .$ That is,

Z_{n} = {[0], [1], [2], \dots, [n - 2], [n - 1]} .

In the case where $n = p$ is a prime, we usually write $Z_{p} .$ (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,

Z_{n}

has several very interesting properties. Like all of our number systems in this class, you can add and multiply elements of

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]$

🔗

Figure 8.1.2. Addition table for

Z_{3}

xxxxxxxxxx
 
@interact
def addition_table_(n=(11,[2..50])):
    P=[[mod(a,n)+mod(b,n) for a in [0..n-1]] for b in [0..n-1]]
    pretty_print(html("The addition table for modulus $%s$"%(n,)))
    pretty_print(html(table(P, header_row = True, frame = True)))

🔗

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. (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]$

🔗

Figure 8.1.3. Multiplication table for

Z_{3}

xxxxxxxxxx
 
@interact
def _(n=(11,[2..50])):
    P=[[mod(a,n)*mod(b,n) for a in [0..n-1]] for b in [0..n-1]]
    pretty_print(html("The multiplication table for modulus $%s$"%(n,)))
    pretty_print(html(table(P, frame=True)))

🔗

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

Z_{n};

recall that this is

{[0], [1], [2], \dots, [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.

🔗

Subsection 8.1.2 Visualization

🔗

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.

Colored multiplication table for $n=7$ — 🔗
Figure 8.1.4. Colored multiplication table for $n = 7$

xxxxxxxxxx
 
@interact
def multiplication_table_plot(n=(7,[2..50])):
    P=matrix_plot(matrix(n,[mod(a,n)*mod(b,n) for a in srange(n) for b in srange(n)]),cmap='jet')
    show(P,figsize=7)

🔗

How does one interpret this graphic? The

a

row and

b

column give the color corresponding to

a \cdot b (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

Z_{n} .

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?

🔗

Subsection 8.1.3 Inverses

🔗

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.

🔗

Fact 8.1.5.

When $p$ is prime, every nonzero element of $Z_{p}$ has an inverse.

🔗

Proof.

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

Z_{p}

is a field, yet another example of bizarre but fun math terminology.)

🔗

What was the command again to get an inverse?

xxxxxxxxxx
 
inverse_mod(26,31)

🔗

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.

xxxxxxxxxx
 
c = mod(26,31)
c^-1

xxxxxxxxxx
 
c = mod(26,31)
c*c^-1

🔗

Go back to the graphics or tables. Can you “see” that there is (exactly one) inverse for every non-zero element of

Z_{p} ?

Number Theory: In Context and Interactive

Section 8.1 The Integers Modulo $n$

Subsection 8.1.1 Definition

Definition 8.1.1. Integers Modulo $n$ .

Subsection 8.1.2 Visualization

Subsection 8.1.3 Inverses

Fact 8.1.5.

Proof.

Section 8.1 The Integers Modulo n

Subsection 8.1.1 Definition

Definition 8.1.1. Integers Modulo n.

Subsection 8.1.2 Visualization

Subsection 8.1.3 Inverses

Fact 8.1.5.

Proof.

Section 8.1 The Integers Modulo $n$

Definition 8.1.1. Integers Modulo $n$ .