# Thread: I can't seem to make Euclidean work backwards either. :/

1. ## I can't seem to make Euclidean work backwards either. :/

Use the extended Euclidean algorithm to find 198^-1 mod 257.

Here's what I have:

257 = 198 x 1 + 59
198 = 59 x 3 + 21
59 = 21 x 2 + 17
21 = 17 x 1 + 4
17 = 4 x 4 + 1

Backwards:
1 = 17 - 4 x 4
1 = 17 - 4 (21 - 17)
1 = 5 x 17 - 4 x 21
1 = 5 x (59 - 21 x 2) - 4 x 21
I worked a little more and think I got this:
1 = 5 x 59 - 14 x 21 (this was by trial and error of some sort)
1 = 5 x 59 - 14 x (198 - 59 x 3)
And I'm stuck again.

And that's where I'm stuck. I'm pretty sure it's having multiplication in the () that's screwing me up, not sure I worked with it before.. and if I have, I just don't get it.

2. Hello,
Here's what I have:

257 = 198 x 1 + 59 (1)
198 = 59 x 3 + 21 (2)
59 = 21 x 2 + 17 (3)
21 = 17 x 1 + 4 (4)
17 = 4 x 4 + 1 (5)

Backwards:
1 = 17 - 4 x 4
1 = 17 - 4 (21 - 17)
1 = 5 x 17 - 4 x 21
1 = 5 x (59 - 21 x 2) - 4 x 21
I worked a little more and think I got this:
1 = 5 x 59 - 14 x 21 (this was by trial and error of some sort)
Yes.

1=5x(59-21x2)-4x21
1=5x59-10x21-4x21
1=5x59-14x21

Then from (2), we have 21=198-59x3
This makes :
1=5x59-14x(198-59x3)
1=5x59-14x198+59x52
1=57x59-14x198

Last step : from (1), we have 59=257-198

1=57x(257-198)-14x198
1=57x257-57x198-14x198
1=57x257-71x198

So -71x198=1-57x257
-71x198=1 mod 257