# Modular Arithmetic

We all learned to tell time when we were very young. It is something that we are familiar with. And for most people it is pretty easy. But, hidden behind this simple idea is a more complicated type of math called **modular arithmetic**. The idea goes like this.

Say you are going on a ski trip. You want to know what time it will be when you arrive at the slopes if you begin driving at **3:00** p.m. and it is a **2 **hour drive. So…

**3 + 2 = 5**

It will be **5:00 **p.m. when you arrive.

What if you were going on a longer road trip? Perhaps to visit your grandparents in another province?

Let’s say that you plan to leave your home at **5:00 **a.m. and it is a **9 **hour drive. What time do you expect to arrive? You would expect to arrive at **2:00 p.m.** Right?

Right! But wait … are you telling me that:

**9 + 5 = 2? **

How can that be when everyone knows that:

**9 + 5 = 14 !**

The point is that on a clock, we use a special way of counting. Once we get to **12** o’clock, the next hour is **1** o’clock, not **13** o’clock. And the next after that is **2** o’clock, not **14** o’clock. But this is just a choice of words. In reality, we could equally well say it was **14** o’clock or **2** o’clock. Either way we would mean **2** hours after **12** o’clock. In that sense, on a clock, **14** means the same thing as **2**.

Does that mean that **14 = 2**? Maybe in a special way it does…

### Congruent Modulo

We can think of it as ‘clock equals.’ Mathematicians have a special way of saying this. They say that two numbers are **congruent modulo** **12** if the difference between the two numbers is **12**, **24**, **36** or any other multiple of **12**. For example, **2** and **14** are congruent modulo **12** because their difference, twelve, is divisible by **12**. This means that on a clock, **2** and **14** mean the same thing. We express this mathematically as:

The mathematical symbol for congruence is **≡**. Here, 2 and 14 are the numbers, and the number in brackets (12) is the **modulus**. Another example of two numbers being congruent modulo **12** is:

because the difference between **39** and **3** is **36**, and **36** is divisible by 12. Not all numbers, however, are congruent modulo 12. For example:

because the difference between **4** and **17** is **13**, and **13** is not divisible by **12**.

Now imagine that we live in a world where the clocks have **7** hours instead

of **12**. This may seem weird but it will give you a chance to try counting using modulo **7**. In this way of counting, we say that two numbers are congruent modulo **7** if their difference is divisible by **7**. For example:

because the difference between them (**9 – 2 = 7**) is divisible by **7**. On the other hand,

because the difference between them (**14 – 2 = 12**) is not divisible by **7**.

Are the following pairs of numbers congruent modulo **7**? Hint: use the 7-hour clock if you need help.

**Question 1: **Does **3 **≡ **9**(mod7)? Why or why not?

Answers are at the bottom of the page.

**Question 2: **Does **1 **≡ **7**(mod7)? Why or why not?

**Question 3: **Does **2** ≡ **16**(mod7)? Why or why not?

### Modulo Arithmetic

Let’s go back to our regular 12 hour clock. In the modulo **12** system, the answer to any calculation we do has to be less than **12**. For example, the first problem in this section was **9+5**. In regular arithmetic, we would say **9+5=14**. In modulo **12** arithmetic, **14** is too big a number to be the answer (it doesn’t appear on a clock). We must, therefore, find its equivalent.

Since we know that the number **14 **is congruent with the number **2**:

**9 + 5 ≡ 2(mod12)**

we give **2(mod12)** as the correct answer for the question **9+5**.

Here is another way that you can think about it using a 12 hour clock again. Starting at 12:00, take the first number and go around the clock 9 positions (for the **9**). Next, go around 5 more positions (for the **5**). Where did you end up? The **2 **position. The **2** is the number in front of the modulus (mod12).

Here is one more way to figure out an addition problem using division. Let’s use **9+5** again. In normal addition, we say **9+5=14**. Divide the modulus (the number in the brackets) into the total.

The remainder (**2**) is what goes in front of the modulus 2 (mod12). What about the number on top? The answer (number of times it divides) is irrelevant for modular arithmetic.

If the two numbers add up to exactly a multiple of the modulus, then you can write either a zero or the number before the modulus:

** 3 + 4 ≡ 0(mod7)**

OR

** 3 + 4 ≡ 7(mod7)**

Mathematicians prefer to use zero, but 7 is also correct in the case above.

Try the following using modulo **7** arithmetic. Keep in mind that your answer should be between **0 **and **6.**

**Question 4: **3 + 18 = ____ (mod7)

**Question 5: **2 + 4 = ____ (mod7)

**Question 6: **19 + 10 = ____ (mod7)

There is, in fact, nothing special about modulo **12** or modulo **7**. We can choose any number to use as a modulus; for example, we could do math in modulo **5999** or **327** or **16** if we wanted to!

## Modular Arithmetic Applications

Modular arithmetic has many applications in cryptography and computer science. It’s often used to detect errors in identification numbers. Think about the kinds of identification numbers we use everyday. Credit cards, bank accounts, and product barcodes all involve long strings of numbers. These numbers need to be correctly exchanged by computer systems. Think about using your credit card to buy something online. Imagine if two of the digits were switched or typed improperly. Modular arithmetic is used to detect these kinds of errors.

To help detect errors, many important numbers include a check digit. This is usually the last digit of a number. It is used as part of a modular arithmetic **algorithm** to check the number for errors. The mod 10 or Luhn algorithm is one that is commonly used. This algorithm involves doubling and then adding all of the digits up in a particular order. The number is correct if the total modulo 10 is equal to 0, meaning it is a multiple of 10. This algorithm is used to validate Canadian Social Insurance Numbers, credit card numbers, and many more. While we may not realize it, we use this kind of modular arithmetic application everyday.

## ANSWERS

**Questions 1**

Does **3** ≡ **9**(mod7)?

3 ≢ 9(mod7)

No, because the difference between them (**9 – 3 = 6**) is not divisible by **7**.

**Questions 2**

Does **1** ≡ **7**(mod7)?

1 ≡ 7(mod7)

No, because the difference between them (**7 – 1 = 6**) is not divisible by **7**.

**Questions 3**

Does **2** ≡ **16**(mod7)?

2 ≡ 16(mod7)

Yes, because the difference between them (**16 – 2 = 14**) is divisible by **7**.

**Questions 4**

**Q103 + 18 = 0(mod7)**

3 + 18 = 21

21 ÷ 7 = 3**R0**. Since there is no remainder, we put a 0 in front of (mod7).

**Questions 5**

**2 + 4 = 6(mod7)**

2 + 4 = 6

6 does not divide evenly by 7. In fact, it does not divide at all; therefore, it has a remainder of itself (**6**) which we put in front of (mod7).

**Questions 6**

**19 + 10 = 1(mod7)**

19 + 10 = 29

29 ÷ 7 = 4**R1**. We put the remainder of **1** in front of (mod7).

## Learn More

ISBN Modular Arithmetic Activity

Practice checking an ISBN using modular arithmetic in this Desmos activity.

Introduction to Modular Arithmetic

The NRICH (University of Cambridge) website has an explanation of modular arithmetic, including a 7-hour clock.

The betterexplained.com website has a comprehensive explanation of modular arithmetic, including ‘clock math’ as was done in this chapter.

## References

GeeksforGeeks. (2020). *Luhn algorithm*.

Lynch, P. (2017, November 2). *Modular arithmetic: you may not know it but you use it every day*. The Irish Times.

Rosetta Code. (n.d.). *Luhn test of credit card numbers*.

Weisstein, Eric W. (n.d.). *Congruence*. Wolfram Math World.