Lesson 6, Topic 3
In Progress

# Questions & Solutions – Modular Arithmetic

Lesson Progress
0% Complete

Example 1

From the multiplication table for arithmetic (mod 6) find the following:

(i) $$\scriptsize 2 \bigotimes x = 3$$

(ii) $$\scriptsize 5 \bigotimes x = 1$$

(iii) $$\scriptsize 0 ⨸ 3$$

(iv) $$\scriptsize 2 ⨸ 5$$

Solution

(i) For $$\scriptsize 2 \: \bigotimes \: x = 3$$

(ii) For $$\scriptsize 5 \: \bigotimes \: x = 1$$

(iii) Let 0 ⨸ 3 = p

i.e. 3p = 0 (mod 5)

From the table p = 0, 2 and 4

(iv) $$\scriptsize 2 ⨸ 5$$

Let 2 ⨸ 5 = p

i.e.   5p = 2

From the table p = 4

Example 2

Find the value(s) of the following:

(i) $$\scriptsize 7 \: \bigotimes \: 9^{-1} \: (mod 17)$$

(ii) $$\scriptsize 20 \: ⨸ \: 8 \: (mod 12)$$

(iii)  $$\scriptsize 1 \: ⨸ \: 2 \: (mod 4)$$

(iv) $$\scriptsize 98 \: ⨸ \: 10 \: (mod 6)$$

Solution

(i) Recall $$\scriptsize 7 \: \bigotimes \: 9^{-1} = 7 \: ⨸ \: 9 \: (mod 17)$$

Let  7 ⨸ 9 = x (mod 17)

i.e.  9x = 7 (mod 17)

9x + 7(17) = 7+ 7(17)(mod 17)

i.e.   9x + 0 = 7 + 119(mod 17)

i.e.    9x = 126(mod 17)

∴      x = 14(mod 17)

(ii) 20 ⨸ 8 (mod 12)

Let 8x = 20(mod 12)

i.e.  8x + 12 = 20 + 12(mod 12)

8x + 0 = 32 (mod 12)   (÷ both sides by 8)

x = 4(mod 12)

Also, for  8x =20(mod 12)

We can have

8x = 12 + 8(mod 12)

i.e.   8x = 0 + 8(mod 12)

i.e. x = 1(mod 12)

In order to get other solution, construct the table of 8x = 20(mod 12)

i.e. table of 8x = 0 + 8(mod 12)

Check for the number 8 on the residues column and the entries on its row, you will find out that the entry number 8 tallies with 1, 4, 7 and 10 on the residues row.

Therefore, the solution for x: 1, 4 ,7 and 10

Hint: Whenever the given modulus is not a prime number, it is possible to have more than one solution, therefore when constructing the table you should take adequate care in resolving the solutions.

(iii) 1 ⨸ 2(mod 4)

i.e. 2x = 1(mod 4)

x does not have a solution in modulo 4.

i.e. x does not exist.

(iv) 98 ⨸ 10 (mod 6)

i.e. 10x = 98(mod 6)

i.e.     (6 + 4x) = (16 × 6 + 2)(mod 6)

i.e.      (0 + 4)x = (0 + 2)(mod 6)

i.e. 4x = 2(mod 6)

i.e.    4x + 6 = 2 + 6(mod 6)

i.e.   4x + 0 = 8 mod 6

4x = 8 mod 6

i.e.     x = 2 mod 6

Also, 4x + 316 = 3(6) +2 (mod 6)

i.e.  4x = 20(mod 6)

i.e.   x = 5 mod 6

∴     the solution for x : 2 and 5

Example 3

Find the multiplicative inverse of the following:

(i) 6(mod 8)

(ii) 3(mod5)

(iii) -2(mod 7)

Solution

(i) 6 mod 8 → the inverse of 6 in (mod 8) is the number such that when it is multiplied by 6 gives 1. However, the inverse of 6 in mod 8 does not exist.

(ii) 3 mod 5 → 3 x 2 = 6 = 1 mod 5

∴the inverse of 3 in mod 5 is 2.

(iii) -2(mod 7)

i.e. -2 = -7 + 5(mod 7)

i.e. -2(mod 7) = 5 mod 7

Therefore, the inverse of 5 in mod 7 is given by

5 × 3 = 15 = 1mod 7

∴   The inverse of 5 in mod 7 is 3.

Example 4

Work out the square root of the following:

(i) $$\scriptsize \sqrt{16} \: (mod 5)$$

(ii) $$\scriptsize \sqrt{64} \: (mod 6)$$

Solution

(i) $$\scriptsize \sqrt{16} = \pm \: 4 mod\: 5$$

4 (mod 5) or -4 (mod 5)

4 (mod 5) or (-5 + 1) (mod 5)

(ii) $$\scriptsize \sqrt{64} = \pm \: 8\: mod 6$$

i.e 8(mod 6) or -8(mod 6)

i.e (6 + 2)(mod 6)or (-12 + 4)(mod 6)

i.e 2(mod 6) or 4(mod 6)

Example 5

Solve the following equations for x

(i) 6x = 18 (mod 10)

(ii) 4x + 1= 5(mod 8)

(iii) 2x + 2 = 3 (mod 4)

(iv) 5x + 2 = 8(mod 11)

Solution

(i) 6x = 18 (mod 10) (÷both sides by 6)

i.e.           x = 3(mod 10)

Also, add 30 to both sides

i.e. (6x + 3 × 10) = 18 + 3 × 10(mod 10)

i.e.  (6x + 0) = 48 (mod 10)

i.e.  6x = 48 (mod 10) (÷both sides by 6)

i.e.   x = 8 (mod 10)

∴   the solution for x : 3 and 8

(ii) 4x + 1 = 5(mod 8) (add 7 to both sides)

i.e.   4x + 1 + 7 = (5 + 7)(mod 8)

i.e. 4x + 8 = 12 (mod 8)

i.e.  4x = 12 (mod 8)       (÷both sides by 4)

i.e.   x = 3 (mod 8)

4x + 1 + 15 = (5+15) mod 8 (add 15 to both sides)

4x + 16 = 20 mod 8

i.e. 4x = 20 mod 8

i.e.   x = 5 mod 8

4x + 1 + 23 = 5 + 23 (mod 8) (add 23 to both sides)

i.e. 4x + 24 = 28 (mod 8)

i.e. 4x = 28 (mod 8) (÷both sides by 4)

i.e.  x = 7 mod 8

4x + 1 + 31 = (5 + 31) (mod 8) (add 31 to both sides)

i.e.   4x + 32 = 36 (mod 8)

i.e.   x = 9 (mod 8)

i.e.   x = (8 + 1) (mod 8)

i.e.  x = 1 (mod 8)

∴   the solution for x: 1, 3, 5 and 7

(iii) 2x + 2 = 3 (mod 4)

For any attempt, you will find out that x does not have a solution for mod 4 arithmetic, therefore x does not exist.

(iv)    5x + 2 = 8 (mod 11) (add 42 to both sides)

i.e. 5x + 2 + 42 = (8 + 42)(mod 11)

i.e. 5x + 44 = 50 (mod 11)

i.e. 5x + 44 = 50 (mod 11)

i.e. 5x + 4(11) = 50(mod 11)

i.e.      5x + 0 = 50(mod 11)            ( ÷both sides by 5)

i.e.      x = 10(mod 11)

Example 6

Simplify the following:

(i) (0 – 4) x (4 + 2)(mod 5)

(ii) 4x + 5 + 8x + 3(mod 7)

Solution

(i) (0 – 4) x (4 + 2) (mod 5)

i.e. -4 × 6(mod 5)

i.e.      (-5 + 1) × (5 + 1)(mod 5)

i.e.      (0 + 1) x (0 + 1)(mod 5)

i.e.       (1 ×1 )(mod 5)

∴   Answer = 1 (mod 5)

(ii)  4x + 5 + 8x +3(mod 7)

12x + 8(mod 7)

(7 + 5)x + (7 + 1)(mod 7)

(0+ 5)x + (0 + 1)(mod 7)

5x + 1(mod 7)

∴    Answer = 5x+1 (mod 7) error: