# 3 Modular arithmetic

## 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.

### 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}.

### 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}.

### 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

### 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 have - so
- (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 have - so

### 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.

### 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.

### 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.