Euclidean Extended Algorithm

[FritoTaco]

Homework Statement

Hi, I'm doing a problem by solving congruences but my question is simply trying to find the inverse of $2 \enspace (mod\enspace 17)$ from $2x \equiv 7(mod \enspace 17)$.

Homework Equations

It's hard to find a definition that makes sense but if you check my upload images you can see exactly what I'm trying to do.
Source:

The Attempt at a Solution

[/B]
Going forwards
1.) $2 = 17(0) + 2$

2.) $17 = 2(8) + 1$

3.) $2 = 1(2) + 0$

Our gcd = 1 which means we can find the inverse starting with step 2.

Going backwards
4.) $1 = 17 - 2(8)$

5.) $2 = 2 - 17(0)$ we wrote this from step 1 by setting the remainder equal to everything else.

6.) $1 = 17 - (2 - 17(0))(8)$ plug in the equation from step 5 into $2$ from step 4.

7.) $1 = 17 - 2(8)$

So our answer says the inverse is 8, but the answer is 9. Where am I messing up?

 

[tnich]

Your answer says 1 = 17 - 2(8) = 17 + 2(-8).
Does that help?

 

[FritoTaco]

Your answer says 1 = 17 - 2(8) = 17 + 2(-8).
Does that help?

Oh, I remember my teacher wrote it like this. So, I'm kinda guessing. But the answer should be between 0 and 17? And just by looking at it 17 - 8 = 9. Is this the reason?

 

[tnich]

That's the reason. You could also say -8 ≡ 9 mod 17.

 

[FritoTaco]

Awesome! Thanks for helping me. There were a few other problems I had the same issue with and couldn't remember what else I was supposed to do, but now it all works.

 

[tnich]

One other thing that I think would help you would be to first write out the linear equation you are trying to solve. In this case, 2x = 1 mod 17 (I think was what you meant to say in the problem statement) implies that 2x + 17y = 1 for some integers x and y. That makes it clear what you are applying Euclid's algorithm to.

 

[FritoTaco]

My teacher never used this method so I don't know if I will actually use it but maybe we will. Thanks!