Question

Find the remainder of 2338when divided by 55. b) What is the inverse of 23 modulo 55 i.e. which number a has the property that 23*a has the remainder 1 when divided by 55?

Answer 1

a) 2338 ≡ 42 • 55 + 28 ≡ 28 (mod 55)

b) We want to find a such that

23a ≡ 1 (mod 55)

Use the Euclidean algorithm:

55 = 2 • 23 + 9

23 = 2 • 9 + 4

9 = 2 • 4 + 1

⇒ 1 = 9 - 2 • 4

⇒ 1 = 9 - 2 • (23 - 2 • 9) = 5 • 9 - 2 • 23

⇒ 1 = 5 • (55 - 2 • 23) - 2 • 23 = 5 • 55 - 12 • 23

Solve for a :

5 • 55 - 12 • 23 ≡ 1 (mod 55)

⇒ -12 • 23 ≡ 1 (mod 55)

⇒ a ≡ -12 ≡ 43 (mod 55)