• Support PF! Buy your school textbooks, materials and every day products Here!

Euclidean Extended Algorithm

  • Thread starter FritoTaco
  • Start date
  • #1
133
23

Homework Statement


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

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.) [itex]2 = 17(0) + 2[/itex]

2.) [itex]17 = 2(8) + 1[/itex]

3.) [itex]2 = 1(2) + 0[/itex]

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

Going backwards
4.) [itex]1 = 17 - 2(8)[/itex]

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

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

7.) [itex]1 = 17 - 2(8)[/itex]

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

Attachments

Answers and Replies

  • #2
tnich
Homework Helper
1,048
336
Your answer says 1 = 17 - 2(8) = 17 + 2(-8).
Does that help?
 
  • Like
Likes FritoTaco
  • #3
133
23
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?
 
  • #4
tnich
Homework Helper
1,048
336
That's the reason. You could also say -8 ≡ 9 mod 17.
 
  • Like
Likes FritoTaco
  • #5
133
23
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.
 
  • #6
tnich
Homework Helper
1,048
336
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.
 
  • Like
Likes FritoTaco
  • #7
133
23
My teacher never used this method so I don't know if I will actually use it but maybe we will. Thanks!
 

Related Threads on Euclidean Extended Algorithm

Replies
0
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
Replies
5
Views
1K
Replies
4
Views
3K
Top