Modular Arithmetic SS1 Mathematics Lesson Note

 INTRODUCTION 

In the previous section, we discovered a new kind of arithmetic, where we add positive integers by rotating in the number cycle. This arithmetic is called modular arithmetic. In our example, we ignored multiples of 4 and concentrated on the remainder. In this case, we say that the modulus is 4.

For example, 

5 = 1 (mod 4)

Where mod 4 means modulus 4 or modulo 4.

Note that 9 ÷ 4 = 2, remainder 1 

And 45 ÷ 4 = 11 remainder 1 

We say that 9 and 45 are equal modulo 4, 

i.e. 9 = 45 = 1 (mod 4)

Example 1 

Reduce 55 to its simplest form: 

Modulo 3

Modulo 4 

Modulo 5

Modulo 6

Solution: 

55 ÷ 3 = 18, remainder 1 

The answer is  55 = 1 (mod 3)

55 ÷ 4 = 13, remainder 3

            The answer is   55 = 3 (mod 4)

55 ÷ 5 = 11, remainder 0

             The answer is  55 = 0 (mod 5)

55 ÷ 6 = 9, remainder 1 

               The answer is 55 = 1 (mod 6)

 CLASSWORK 

Write down the names of four markets in your locality which are held in rotation over 4* days. 

ADDITION, SUBSTRACTION AND MULTIPLICATION OPERATIONS IN MODULO ARITHMETIC 

Addition and Subtraction 

The table below shows an addition table (mod 4) in which numbers 0, 1, 2 and 3 are added to themselves. 

In the table, multiples of 4 are ignored and remainders are written down. For example 2 ⨁ 3 = 5 = 1 (mod 4) and 2 ⨁ 2 = 4 = 0 (mod 4.) note that we often use the symbol ⨁ to show addition in modular arithmetic.

 Example 1 

Find 

1. 0 ⨁ 3 (mod 4),    
2. 1 ⨁ 2 (mod 4)

Solution:

Start at 0 and move in an anticlockwise direction in three places. 

The result is 1.

Therefore, 0 ⨁ 3 = 1 (mod 4)

Start at 1 and move in an anticlockwise direction in two places. The result is 3. 

Therefore, 1 ⨁ 2 = 3 (mod 4).

Example 2 

Add 39 ⨁ 29 (mod 6)

There are two ways to solve this.

Solution 1: 39 ⨁ 29 = 68

    = (6 x 11 + 2)

    = 2 (mod 6)

Solution 2: By expressing both numbers in mod 6

39 ⨁ 29 = (6 x 6 + 3) + (6 x 4 + 5)

    = (3 + 5) (mod 6)

    = 8 (mod 6)

    =2 (mod 6)

2. Multiplication of Modulo

Example 1 

Evaluate the following, modulo 4,

2 ⨂ 2         b. 3 ⨂ 2        c. 33 ⨂ 9

Solution:

2 ⨂ 2 = 4 (mod 4)

3 ⨂ 2 = 4 + 2 = 2 (mod 4)

33 ⨂ 9 = 297 = 4 x 74 + 1 = 1 (mod 4) Or expressing both numbers in mod 4 

33 ⨂ 9 = 1 x 1 (mod 4)

        = 1 (mod 4)

Example 2 

Evaluate the following in the given moduli.

16 ⨂ 7 (mod 5) b. 18 ⨂ 17 (mod 3)

1. 16 ⨂ 7 = 112

    = 22 ⨂ 5 + 2

    = 2 (mod 5)

or

16 = 15 + 1 = 1 (mod 5)

7 = 5 + 2 = 2 (mod 5)

16 ⨂ 7 = 1 ⨂ 2 (mod 5)

    = 2 (mod 5)

b.18 ⨂ 7 (mod 3)

18 = 0 (mod 3)

17 = 2 (mod 3)

18 ⨂ 17 = 0 ⨂ 2 (mod 3)

        = 0 (mod 3)

In examples 1 and 2, it can be seen that it is usually most convenient to convert the given numbers to their simplest form before calculation. 

CLASSWORK 

1. Find the following numbers in their simplest form, modulo 4. 

a.15 

1. 102
2. 38

2. Find the values in the moduli written beside them.

a.16 ⨂ 7 (mod 5)

1. 80 ⨂ 29 (mod 7)
2. 21 ⨂ 18 (mod 10)

ASSIGNMENT

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

3. Find the values in the moduli written beside them. 
4. 8 ⨂ 25 (mod 3) 
5. 2     B. 5     C. 9    D. 4

1. 27 ⨂ 4 (mod 7)A. 7     B. 5     C. 1    D. 3

iii. 21 ⨂ 65 (mod 4)  A. 1    B. 9      C. 4     D. 8 

4. Calculate the following  
5. 42 ⨁28 (mod 8)

1. 12 ⨁ 9 (mod 4)

5. Complete the multiplication modulo 6