Modular Arithmetic – SS1 Mathematics Lesson Note (First Term)

Modular arithmetic is arithmetic in which we ignore multiples of a chosen number, called the modulus, and keep only the remainder.

Behavioural objectives

1. Explain what modulus means in modular arithmetic.
2. Reduce a number to its simplest form in a given modulus.
3. Add numbers in modular arithmetic.
4. Multiply numbers in modular arithmetic.
5. Complete an addition or multiplication table in a given modulus.

What is modular arithmetic?

Modular arithmetic is a kind of arithmetic that works with remainders after division by a fixed number, the modulus.

• Modulus: the number we divide by and whose multiples we ignore, for example 4 in “mod 4”.
• Mod 4: short for “modulus 4” or “modulo 4”.
• Simplest form: the remainder, a whole number from 0 up to one less than the modulus.
• Symbol ⨁: shows addition in modular arithmetic.
• Symbol ⨂: shows multiplication in modular arithmetic.

How does the number cycle work?

• In mod 4 we use only the numbers 0, 1, 2 and 3.
• After 3 we return to 0, so the numbers go round in a cycle.
• Adding means moving forward round the cycle.

What are some examples of equal numbers in a modulus?

• 5 = 1 (mod 4): 5 ÷ 4 = 1, remainder 1.
• 9 = 1 (mod 4): 9 ÷ 4 = 2, remainder 1.
• 45 = 1 (mod 4): 45 ÷ 4 = 11, remainder 1.
• 9 = 45 = 1 (mod 4): 9 and 45 leave the same remainder, so they are equal modulo 4.

How do we reduce a number to its simplest form?

To reduce a number, divide it by the modulus and keep the remainder.

1. Divide the number by the modulus.
2. Find the remainder.
3. Write the remainder with the modulus, for example 1 (mod 3).

Example 1: reducing a number

Reduce 55 to its simplest form in each of these moduli: 3, 4, 5 and 6.

• Mod 3: 55 ÷ 3 = 18, remainder 1. So 55 = 1 (mod 3).
• Mod 4: 55 ÷ 4 = 13, remainder 3. So 55 = 3 (mod 4).
• Mod 5: 55 ÷ 5 = 11, remainder 0. So 55 = 0 (mod 5).
• Mod 6: 55 ÷ 6 = 9, remainder 1. So 55 = 1 (mod 6).

How do we reduce a negative number?

To reduce a negative number, add multiples of the modulus until the answer lies from 0 to one less than the modulus.

1. Find a multiple of the modulus just above the number.
2. Add that multiple to the negative number.
3. Write the answer with the modulus.

Example 2: reducing negative numbers

• -9 (mod 4): -9 + 12 = 3, so -9 = 3 (mod 4).
• -20 (mod 6): -20 + 24 = 4, so -20 = 4 (mod 6).

Classwork

• Write down the names of four markets in your locality which are held in rotation over 4 days.
• Link the four market days to the numbers 0, 1, 2 and 3 in mod 4.

How do we add in modular arithmetic?

To add in modular arithmetic, add the numbers and keep only the remainder after dividing by the modulus.

1. Add the two numbers in the usual way.
2. Divide the sum by the modulus.
3. Write down the remainder.

What does the addition table (mod 4) look like?

The table below shows the numbers 0, 1, 2 and 3 added to one another in mod 4.

• 2 ⨁ 3: 2 + 3 = 5 = 1 (mod 4).
• 2 ⨁ 2: 2 + 2 = 4 = 0 (mod 4).

Example 1

Find 0 ⨁ 3 and 1 ⨁ 2 in mod 4.

• 0 ⨁ 3: start at 0 and move forward three places round the cycle (1, 2, 3). So 0 ⨁ 3 = 3 (mod 4).
• 1 ⨁ 2: start at 1 and move forward two places (2, 3). So 1 ⨁ 2 = 3 (mod 4).

Example 2

Add 39 ⨁ 29 (mod 6). There are two ways to solve it.

Solution 1: add first, then reduce.

• 39 ⨁ 29 = 68
• 68 = (6 × 11 + 2)
• So the answer is 2 (mod 6).

Solution 2: reduce both numbers first.

• 39 ⨁ 29 = (6 × 6 + 3) + (6 × 4 + 5)
• = (3 + 5) (mod 6)
• = 8 (mod 6)
• = 2 (mod 6)

How do we multiply in modular arithmetic?

To multiply in modular arithmetic, multiply the numbers, then keep only the remainder after dividing by the modulus.

1. Multiply the two numbers.
2. Divide the product by the modulus.
3. Write down the remainder.

Example 1

Evaluate 2 ⨂ 2, 3 ⨂ 2 and 33 ⨂ 9 in mod 4.

• 2 ⨂ 2: 4 = 0 (mod 4).
• 3 ⨂ 2: 6 = 4 + 2 = 2 (mod 4).
• 33 ⨂ 9: 297 = 4 × 74 + 1 = 1 (mod 4).
• Shorter way: 33 = 1 (mod 4) and 9 = 1 (mod 4), so 33 ⨂ 9 = 1 ⨂ 1 = 1 (mod 4).

Example 2

Evaluate 16 ⨂ 7 (mod 5) and 18 ⨂ 17 (mod 3).

(a) 16 ⨂ 7 (mod 5)

• 16 ⨂ 7 = 112 = (5 × 22) + 2 = 2 (mod 5).
• Or: 16 = 15 + 1 = 1 (mod 5) and 7 = 5 + 2 = 2 (mod 5).
• 16 ⨂ 7 = 1 ⨂ 2 = 2 (mod 5).

(b) 18 ⨂ 17 (mod 3)

• 18 = 0 (mod 3) and 17 = 2 (mod 3).
• 18 ⨂ 17 = 0 ⨂ 2 = 0 (mod 3).

• Tip: reduce the given numbers to their simplest form before you calculate. The numbers become smaller and easier to handle.

What does the multiplication table (mod 4) look like?

• 3 ⨂ 3: 9 = 8 + 1 = 1 (mod 4).
• 2 ⨂ 3: 6 = 4 + 2 = 2 (mod 4).

Evaluation

1. Find the following numbers in their simplest form, modulo 4.
   • (a) 15
   • (b) 102
   • (c) 38
2. Find the values in the moduli written beside them.
   • (a) 16 ⨂ 7 (mod 5)
   • (b) 80 ⨂ 29 (mod 7)
   • (c) 21 ⨂ 18 (mod 10)
3. Calculate 17 ⨁ 20 (mod 6).
4. Reduce -13 to its simplest form in mod 5.

Assignment

Answer all the questions below in your exercise book.

Find the simplest form of the following in the given moduli.

1. -75 (mod 7): A. 4 B. 2 C. 5 D. 7
2. -56 (mod 13): A. 10 B. 5 C. 9 D. 12

Find the values in the moduli written beside them.

3. 8 ⨂ 25 (mod 3): A. 2 B. 5 C. 9 D. 4
4. 27 ⨂ 4 (mod 7): A. 7 B. 5 C. 1 D. 3
5. 21 ⨂ 65 (mod 4): A. 1 B. 9 C. 4 D. 8

Calculate the following.

6. 42 ⨁ 28 (mod 8)
7. 12 ⨁ 9 (mod 4)

Complete the multiplication table modulo 6.

8. Copy and complete the table below.