# 3.5 Further exercises

## Exercise 51

Evaluate the following sums and products in modular arithmetic.

(a) 21 +

_{26}15, 21 ×_{26}15.(b) 19 +

_{33}14, 19 ×_{33}14.

### Answer

### Solution

(a) 21 +

_{26}15 = 10, 21 ×_{26}15 = 3.(b) 19 +

_{33}14 = 0, 19 ×_{33}14 = 2.

## Exercise 52

Use Euclid's Algorithm to find:

(a) the multiplicative inverse of 8 in

_{21};(b) the multiplicative inverse of 19 in

_{33}.

### Answer

### Solution

(a)

Hence

Hence 8 × 8 = 3 × 21 + 1, so

so the multiplicative inverse of 8 in

_{21}is 8.(b)

Hence

Hence

so

so the multiplicative inverse of 19 in

_{33}is 7.

## Exercise 53

Construct the multiplication table for _{11}, and hence find the multiplicative inverse of every non-zero element in _{11}.

### Answer

### Solution

Hence we have the following multiplicative inverses in _{11}.

## Exercise 54

Use the solution to Exercise 52 to solve the following equations.

(a) 8 ×

_{21}*x*= 13(b) 19 ×

_{33}*x*= 15

### Answer

### Solution

(a) We have 8 ×

_{21}*x*= 13. Multiplying by 8, which is the multiplicative inverse of 8 mod 21 (see the solution to Exercise 52(a)), we haveso

(b) We have 19 ×

_{33}*x*= 15. Multiplying by 7, which is the multiplicative inverse of 19 mod 33 (see the solution to Exercise 52(b)), we haveso

## Exercise 55

Find all the solutions of the following equations.

(a) In

_{8}: 3 ×_{8}*x*= 7, 4 ×_{8}*x*= 7, 4 ×_{8}*x*= 4.(b) In

_{15}: 3 ×_{15}*x*= 6, 4 ×_{15}*x*= 3, 5 ×_{15}*x*= 2.

### Answer

### Solution

(a) Because 3 and 8 are coprime, the equation 3 ×

_{8}*x*= 7 has a unique solution. The solution,*x*= 5, can be found in various ways: for example, by calculating*x*= 3^{−1}×_{8}7, or by testing possible values for*x*, or by spotting that 7 ≡ 15 (mod 8) and using the fact that the congruence 3 × 5 ≡ 15 (mod 8) implies 3 × 5 ≡ 7 (mod 8) giving 3 ×_{8}5 = 7.The equation 4 ×

_{8}*x*= 7 has no solutions because 4 and 8 have common factor 4 but 7 does not.One solution of the equation 4 ×

_{8}*x*= 4 is*x*= 1. Also*n*/*d*= 8/4 = 2, so the other solutions are*x*= 1 + 2 = 3,*x*= 1 + 4 = 5 and*x*= 1 + 6 = 7.(b) One solution of the equation 3 ×

_{15}*x*= 6 is*x*= 2. Also*n*/*d*= 15/3 = 5, so the other solutions are*x*= 2 + 5 = 7 and*x*= 2 + 10 = 12.Because 4 and 15 are coprime, the equation 4 ×

_{15}*x*= 3 has a unique solution. The solution,*x*= 12, can be found in various ways: for example, by calculating*x*= 4^{−1}×_{15}3, or by testing possible values for*x*, or by spotting that 3 ≡ −12 (mod 15) and using the fact that the congruence 4 × (−3) ≡ −12 (mod 15) implies 4 × 12 ≡ 3 (mod 15) giving 4 ×_{15}12 = 3.The equation 5 ×

_{15}*x*= 2 has no solutions because 5 and 15 have common factor 5 but 2 does not.

## Exercise 56

(a) Show that the equation

*x*×_{12}*x*= 7 has no solutions.(b) Find all the solutions of

*x*×_{12}*x*= 4.

### Answer

### Solution

We find all the values of *x* ×_{12}*x*.

(a) Hence there is no integer

*x*_{12}such that*x*×_{12}*x*= 7.(b) The solutions of

*x*×_{12}*x*= 4 are*x*= 2, 4, 8, 10.