Zn vs. Z/nZ

If you read papers about cryptography, you'll see the mathematical structure where integers are added modulo n written two different ways. Computer scientists tend to write this as Zn while mathematicians tend to write this as ℤ/nℤ. I've explained this so many times in the past year or so that I've decided to put an explanation here that I can just point people to in the future.

The notation Zn is fairly easy to understand. It's just the set {0,1,…,n-1} along with addition modulo n. The notation ℤ/nℤ is a bit trickier.

If we write the integers as ℤ where

ℤ = {…,-1,0,1,…}

then we can write

nℤ = {…,-n,0,n,…}

Elements of ℤ/nℤ are nℤ along with

1 + nℤ = {…,-n+1,1,n+1,…}

2 + nℤ = {…,-n+2,2,n+2,…}

along with an operation on ℤ/nℤ that acts just like addition, where we have that

(a + nℤ) + (b + nℤ) = (a + b) + n

It should be fairly clear that we can identify elements of Zn with elements of ℤ/nℤ in the obvious way, with a∈Zn corresponding to a + nZ∈ℤ/nℤ. Because they mean essentially the same thing, why would anyone want to use the more cumbersome ℤ/nℤ notation?

It turns out that there are lots of mathematical objects that have structure that lets you define operations on them that aren't division but that behave much like division does. In the case of group theory, for example, the third isomorphism theorem says that when some technical conditions are satisfied for groups G, H and K then we can write

(G/K) / (H/K) ≅ G/H

where the "≅" symbol indicates that the two structures are isomorphic, or essentially the same, just like Zn and ℤ/nℤ are. So while the mathematical notation may be both cumbersome and confusing, it actually can be a good way to show that there's additional structure present that the simpler notation doesn't suggest.

Leave a Reply

Your email address will not be published. Required fields are marked *