Advanced High-School Mathematics

90 CHAPTER 2 Discrete Mathematics

18 = 3·5 + 3

5 = 1·3 + 2

3 = 1·2 + 1.

Now work backwards and get

2 · 18 − 7 ·5 = 1.

This says that the inverse of 5 modulo 18 is−7. Therefore we see that
the solution of the above is

x≡− 7 · 14 ≡(−7)(−4)≡ 28 ≡10(mod 18).

Exercise

1. Solve the linear congruences

(a) 17x≡4(mod 56)

(b) 26x≡7(mod 15)

(c) 18x≡9(mod 55)

2.1.8 Alternative number bases

In writing positive integers, we typically write in base 10, meaning
that the digits represent multiples of powers of 10. For instance, the
integer 2,396 is a compact way of writing the sum

2 ,396 = 6· 100 + 9· 101 + 3· 103 + 2· 102.

In a similar way, decimal numbers, such as 734.865 likewise represent
sums of (possibly negative) powers of 10:

734 .865 = 5· 10 −^3 + 6· 10 −^2 + 8· 10 −^1 + 4· 100 + 3· 101 + 7· 102.