Previous, Math 511 Home, Contents, Next

Modular Arithmetic

RSA public key cryptography and the secure socket layer are the primary means of securing communications over the World Wide Web. These algorithms are built on modular arithmetic, our first topic. We will spend about two weeks on the properties of Zn, the integers mod n. After building up the background, we will then spend a week or two discussing how to send secure messages to a web site without any prior communications to establish the code you use.

Zn is the algebraic structure consisting of the set {0, 1, 2, ..., n-1} with the operations of addition and multiplication, but Zn is arithmetic on the number circle, rather then the number line. So addition is just counting on, the same as with regular addition, but now whenever you count past n-1 you start over again at 0. Learning to answer questions about what time is it 3 hours after 11:00 is learning to do arithmetic mod 12, except that we prefer to speak of 12 o’clock rather than 0 o’clock. While clock arithmetic is Z12, you can work with any modulus you want. The addition and multiplication tables for Z4 and Z5 are given below.

Arithmetic mod 4

+

0

1

2

3

    

´

0

1

2

3

0

0

1

2

3

    

0

0

0

0

0

1

1

2

3

0

    

1

0

1

2

3

2

2

3

0

1

    

2

0

2

0

2

3

3

0

1

2

    

3

0

3

2

1

 

 

Arithmetic mod 5

+

0

1

2

3

4

    

´

0

1

2

3

4

0

0

1

2

3

4

    

0

0

0

0

0

0

1

1

2

3

4

0

    

1

0

1

2

3

4

2

2

3

4

0

1

    

2

0

2

4

1

3

3

3

4

0

1

2

    

3

0

3

1

4

2

4

4

0

1

2

3

    

4

0

4

3

2

1

Field laws 1-7 and 9 will be satisfied for Zn for any choice of n (we will prove this later). The technical term for an algebraic structure satisfying laws 1-7 and 9 is a commutative ring with identity. We will discuss the naming of these types of structures later on. For now, we are concerned with fields. If law 8, the existence of multiplicative inverses, is also satisfied, then Zn will be a field. We can see that Z5 has multiplicative inverses, because every element other than 0 has a 1 somewhere in its row in the multiplication table. So 1-1 = 1, 2-1 = 3, 3-1 = 2, and 4-1 = 4. On the other hand, Z4 is not a field because 2 has no inverse, there is no element which gives 1 when multiplied by 2 mod 4.

This raises the question of which values of n make Zn a field, which gives us our first two homework problems.

  1. For what values of n (2 £ n £ 9) is Zn a field?
  2. Based on your answer to problem 1, conjecture a rule for which values of n make Zn a field.
  3. Z10 is not a field. Which elements of Z10 have multiplicative inverses?
  4. Z15 is not a field. Which elements of Z15 have multiplicative inverses?
  5. Can you conjecture a rule for which elements of Zn have multiplicative inverses?
For problem 1, justify your answer for each n either by listing all the inverses mod n (as we did for Z5) or by listing an element that doesn’t have an inverse mod n (as we did for Z4). For problem 2, just give your conjecture and verify that it works for 2 £ n £ 9. Of course, once you have a conjecture you need to start thinking about why it might be true. Since all the field laws except the existence of multiplicative inverses are automatically satisfied for any Zn, asking why some Zn aren’t fields is the same as asking why some elements don’t have inverses mod n. To get a grip on this question, we look at the cases of Z10 and Z15 in problems 3 and 4. Just list which elements don’t have multiplicative inverses in each case. With this data, you should be able to conjecture a general rule for which elements have inverses. Give your conjecture for problem 5 and verify that your rule works for the elements of Z10 and Z15. Then check that your rule for the existence of multiplicative inverses in problem 5 justifies your conjecture for which values of n make Zn a field (in problem 2).

Please report any problems with this page to bennett@math.ksu.edu
© 1998, Andrew G. Bennett