Using the Euclidean Algorithm to solve 13 in Z30

30 = 2x13+4

13= 3x4+1

Eliminating multiples of four

1= 13-3x4

= 13-3(30-2x13)

= 7x13-3x30 ----How was this achieved?

Thanks

Printable View

- August 13th 2010, 11:16 AMmark090480Euclidean Algorithm
Using the Euclidean Algorithm to solve 13 in Z30

30 = 2x13+4

13= 3x4+1

Eliminating multiples of four

1= 13-3x4

= 13-3(30-2x13)

= 7x13-3x30 ----**How was this achieved?**

Thanks - August 14th 2010, 04:48 AMDefunkt
- August 14th 2010, 06:17 AMHallsofIvy
- September 14th 2010, 07:53 AMmark090480
Could you explain what is going on here? I don't understand why we do it in that way. My maths books just tells me how and not why. Thanks.