Question

3. (a) Find the greatest common divisor of 34 and 89 using the Euclidean algo rithm.

Answer 1

a. We have GCD(34, 89) = 1; using the Euclidean algorithm,

89 = 2•34 + 21

34 = 1•21 + 13

21 = 1•13 + 8

13 = 1•8 + 5

8 = 1•5 + 3

5 = 1•3 + 2

3 = 1•2 + 1

b. Working backwards,

1 = 3 - 2

1 = 3 - (5 - 3) = 2•3 - 5

1 = 2•(8 - 5) - 5 = 2•8 - 3•5

1 = 2•8 - 3•(13 - 8) = 5•8 - 3•13

1 = 5•(21 - 13) - 3•13 = 5•21 - 8•13

1 = 5•21 - 8•(34 - 21) = 13•21 - 8•34

1 = 13•(89 - 2•34) - 8•34 = 13•89 - 34•34

c. Using the linear combination find in part b,

1 ≡ 13•89 - 34•34 (mod 89)

1 ≡ (-34)•34 (mod 89)

and

-34 ≡ -34 + 89 ≡ 55 (mod 89)

So, the inverse of 34 modulo 89 is 55.

d. Multiply both sides of the congruence by the inverse of 34:

55•34x ≡ 55•53 (mod 89)

x ≡ 2915 ≡ 32•89 + 67 ≡ 67 (mod 89)